Абстракция моей проблемы заключается в том, что на декартовой плоскости много прямоугольников. Эти прямоугольники имеют известные целочисленные размеры и должны иметь целочисленные координаты, их абсциссы (горизонтальные координаты) известны и фиксированы, могут различаться только их ординаты (вертикальные координаты).
Задача состоит в том, чтобы найти те ординаты, для которых наименьший прямоугольник, содержащий все заданные прямоугольники, является минимальным. Это означает, что он должен иметь минимальную высоту, так как его ширина фиксирована, поскольку маленькие прямоугольники имеют фиксированные оси абсцисс.
Я не знаю, следует ли мне использовать поиск с возвратом или есть более быстрый способ, я могу представить, что при 50 прямоугольниках потребуется некоторое измеримое время для вычисления правильного решения, и жадный алгоритм мне не подходит.
Редактировать: Извините, теперь я понимаю, что выразился недостаточно ясно. Когда я впервые задал этот вопрос, я создавал приложение-календарь. Менеджер заполнял события для своей команды:
- событие А начинается с 14:00. и заканчивается в 16:00.
- событие B начинается с 17:00. и заканчивается в 18:00.
- событие C начинается с 16:00. и заканчивается в 18:00.
- событие D начинается с 14:00. и заканчивается в 15:00.
- событие E начинается с 15:00. и заканчивается в 17:00.
Я хочу отображать эти события на временной шкале, и я хочу, чтобы они занимали как можно меньше места на экране, не перекрываясь (поскольку менеджер хочет видеть каждое событие в своем прямоугольнике и видеть описание в этом прямоугольнике).
Наилучшей компоновкой для приведенного выше примера будет следующая:
+-----+-----+
| A | C |
+---+-+-+---+
| D | E | B |
+---+---+---+
A и C находятся на одной линии, D, E, B — на другой. Жадный подход поместил бы A и B на одну строку, C и D на другую строку, а E на третью строку.
