Разбор задачи «Контейнеры для музея»

Идея задачи

Даны n прямоугольных контейнеров. Для каждого известны его ширина w и высота h.

Один контейнер можно вложить в другой тогда и только тогда, когда обе его стороны строго меньше соответствующих сторон внешнего контейнера:

• w1 < w2
• h1 < h2

Нужно найти максимальное количество контейнеров, которые можно вложить друг в друга.

Наивный подход

Сразу возникает стандартная динамика:

• отсортировать контейнеры
• dp[i] — максимальная длина цепочки, оканчивающейся в i-м контейнере
• перебрать все j < i и проверить, можно ли перейти из j в i

Тогда

dp[i] = 1 + max(dp[j]), где wj < wi и hj < hi

Такое решение работает за O(n^2).

Если n маленькое, этого было бы достаточно. Но в задаче ограничения большие, поэтому нужен более быстрый подход.

Ключевое наблюдение

Если бы контейнеры были уже упорядочены по ширине, то осталось бы только следить за высотой.

Кажется, что можно:

1. отсортировать контейнеры по ширине
2. найти наибольшую строго возрастающую подпоследовательность по высотам

Но здесь есть важная тонкость.

Почему обычной сортировки по (w, h) недостаточно

Рассмотрим контейнеры:

• (2, 3)
• (2, 4)

Ширины равны, значит один в другой вложить нельзя.

Но если отсортировать их по возрастанию и затем смотреть только на высоты, получим возрастающую последовательность 3, 4. Алгоритм LIS ошибочно решит, что оба контейнера можно взять в одну цепочку.

Значит, контейнеры с одинаковой шириной нужно обрабатывать особым образом.

Правильная сортировка

Сортируем контейнеры так:

• по ширине — по возрастанию
• при равной ширине — по высоте по убыванию

То есть порядок такой:

• (2, 5)
• (2, 4)
• (2, 3)

Теперь контейнеры с одинаковой шириной не смогут одновременно попасть в строго возрастающую подпоследовательность по высотам.

Это и есть главный прием задачи.

Почему после этого задача сводится к LIS

После сортировки:

• ширины идут по неубыванию
• одинаковые ширины расположены так, что высоты внутри группы идут по убыванию

Теперь, если мы нашли строго возрастающую подпоследовательность по высотам, то:

• одинаковые ширины в нее не попадут одновременно
• значит, для выбранных элементов ширины тоже будут строго возрастать

Следовательно, такая подпоследовательность действительно задает корректную цепочку вложений.

И наоборот: любая допустимая цепочка вложений после сортировки сохранит порядок и даст строго возрастающую последовательность высот.

Значит, задача полностью сводится к поиску длины LIS по высотам.

Как искать LIS за O(n log n)

Будем поддерживать массив d.

Смысл массива:

• d[len] — минимально возможная последняя высота возрастающей подпоследовательности длины len + 1

Как обновлять d

Идем по всем высотам слева направо.

Для текущей высоты h:

• находим первую позицию pos, где d[pos] >= h
• если такой позиции нет, добавляем h в конец массива
• иначе заменяем d[pos] = h

Почему это правильно:

• мы не обязаны хранить саму подпоследовательность
• достаточно хранить наилучший возможный «хвост» для каждой длины
• чем меньше хвост, тем легче потом продолжить последовательность

Длина массива d в конце и будет ответом.

Разберем на примере

Пусть контейнеры такие:

• (5, 4)
• (6, 4)
• (6, 7)
• (2, 3)

После сортировки по правилу:

• (2, 3)
• (5, 4)
• (6, 7)
• (6, 4)

Высоты:

3, 4, 7, 4

Ищем LIS:

1. 3 → d = [3]
2. 4 → d = [3, 4]
3. 7 → d = [3, 4, 7]
4. 4 → заменяем первую позицию >= 4 → d = [3, 4, 7]

Ответ: 3

Например, подходит цепочка:

(2, 3) -> (5, 4) -> (6, 7)

Алгоритм

1. Считать все контейнеры.

2. Отсортировать по правилу:

   • w по возрастанию
   • при равных w — h по убыванию
3. Взять последовательность высот.
4. Найти длину LIS по этой последовательности с помощью бинарного поиска.
5. Вывести ответ.

Доказательство корректности

Докажем, что описанный алгоритм действительно находит максимальную длину цепочки.

Лемма 1

После сортировки по ширине по возрастанию и по высоте по убыванию при равных ширинах никакие два контейнера с одинаковой шириной не могут одновременно входить в строго возрастающую подпоследовательность по высотам.

Доказательство. Пусть два контейнера имеют одинаковую ширину. Тогда после сортировки контейнер с большей высотой идет раньше контейнера с меньшей высотой. Значит, в последовательности высот внутри такой группы идет невозрастающий порядок. Следовательно, два элемента из этой группы не могут одновременно образовать строго возрастающий фрагмент. Лемма доказана.

Лемма 2

Любая строго возрастающая подпоследовательность высот после такой сортировки соответствует корректной цепочке вложений.

Доказательство. Высоты в подпоследовательности строго возрастают. По лемме 1 одинаковые ширины не могут попасть в такую подпоследовательность вместе, значит ширины у выбранных контейнеров тоже строго возрастают. Следовательно, каждая следующая пара имеет и большую ширину, и большую высоту. Значит, контейнеры можно вложить друг в друга. Лемма доказана.

Лемма 3

Любая корректная цепочка вложений дает строго возрастающую подпоследовательность высот после сортировки.

Доказательство. В корректной цепочке и ширины, и высоты строго возрастают. После сортировки по ширине порядок таких контейнеров не нарушится. Следовательно, их высоты образуют строго возрастающую подпоследовательность. Лемма доказана.

Теорема

Ответ задачи равен длине LIS по высотам после описанной сортировки.

Доказательство. Из леммы 2 следует, что любая LIS дает допустимую цепочку. Из леммы 3 следует, что любая допустимая цепочка соответствует возрастающей подпоследовательности. Значит, максимальные длины совпадают. Теорема доказана.

Сложность

• сортировка: O(n log n)
• поиск LIS: O(n log n)
• память: O(n)

Итоговая сложность:

O(n log n) по времени и O(n) по памяти.

Эталонное решение на C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> envelopes(n);
    for (int i = 0; i < n; i++) {
        cin >> envelopes[i].first >> envelopes[i].second;
    }

    sort(envelopes.begin(), envelopes.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second > b.second;
    });

    vector<int> d;

    for (int i = 0; i < n; i++) {
        int h = envelopes[i].second;
        auto it = lower_bound(d.begin(), d.end(), h);

        if (it == d.end()) {
            d.push_back(h);
        } else {
            *it = h;
        }
    }

    cout << d.size() << '\n';
    return 0;
}

Эталонное решение на Python

from bisect import bisect_left

n = int(input())
envelopes = []

for _ in range(n):
    w, h = map(int, input().split())
    envelopes.append((w, h))

envelopes.sort(key=lambda x: (x[0], -x[1]))

d = []

for w, h in envelopes:
    pos = bisect_left(d, h)
    if pos == len(d):
        d.append(h)
    else:
        d[pos] = h

print(len(d))

Что важно не перепутать

1. При равной ширине нужно сортировать по высоте по убыванию

Это главный подводный камень задачи.

Неправильно:

• сортировать просто по (w, h) по возрастанию

Правильно:

• по w вверх
• при равных w по h вниз

2. В LIS нужен именно lower_bound / bisect_left

Мы ищем строго возрастающую подпоследовательность.

Поэтому для текущей высоты h нужно найти первую позицию, где значение не меньше h.

3. Не нужно проверять вложение всех пар явно

После правильной сортировки задача уже сведена к одномерной LIS по высотам.

Решение попроще: динамика за O(n^2)

Иногда полезно сначала понять более простой вариант.

После той же сортировки можно сделать так:

• dp[i] = 1
• для каждого i перебрать все j < i
• если h[j] < h[i], то обновить dp[i]

То есть:

dp[i] = max(dp[i], dp[j] + 1)

Это проще для понимания, но медленнее.

Пример такого решения на C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<pair<int, int>> envelopes(n);
    for (int i = 0; i < n; i++) {
        cin >> envelopes[i].first >> envelopes[i].second;
    }

    sort(envelopes.begin(), envelopes.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        if (a.first != b.first) return a.first < b.first;
        return a.second > b.second;
    });

    vector<int> dp(n, 1);
    int ans = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (envelopes[j].second < envelopes[i].second) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }

    cout << ans << '\n';
    return 0;
}

Когда какое решение использовать

• Если ограничения маленькие, подойдет O(n^2).
• Если ограничения большие, нужно решение через LIS за O(n log n).

Для этой задачи эталонным является именно второй вариант.

Вывод

В этой задаче главное — заметить правильное преобразование:

• не пытаться напрямую строить двумерную динамику
• сначала аккуратно отсортировать контейнеры
• затем свести задачу к поиску LIS по высотам

Это классическая и очень важная идея: задача на двумерное сравнение после правильной сортировки превращается в одномерную задачу на наибольшую возрастающую подпоследовательность.