Можно ли избежать возврата при попытке минимизировать пространство прямоугольника, которое включает в себя прямоугольники различных целочисленных форм?

Question

Абстракция моей проблемы состоит в том, что в декартовой плоскости много прямоугольников.Эти прямоугольники имеют известные целочисленные размеры и должны иметь целочисленные координаты, их абсциссы (горизонтальные координаты) известны и фиксированы, могут изменяться только их ординаты (вертикальные координаты).

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

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

Редактировать: Извините, теперь я понимаю, что я неДостаточно ясно.Когда я впервые задал этот вопрос, я создавал приложение для календаря.Менеджер будет заполнять события для своей команды:

• событие A начинается с 14:00.и заканчивается в 16:00. * 10101
• событие B начинается с 17:00.и заканчивается в 18:00. * 10101
• событие C начинается с 16:00.и заканчивается в 18:00.
• событие E начинается с 15:00.и заканчивается в 17:00.

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

Лучшее расположение для приведенного выше примера будет следующим:

+-----+-----+
|  A  |  C  |
+---+-+-+---+
| D | E | B |
+---+---+---+

A и C находятся на линии, D,E, B находятся на другом.Жадный подход поместил бы А и В в одну строку, С и D - в другую, а Е - в третью.

Answer 1

Я бы поддерживал хронологический порядок событий.Вы строите календарь, поэтому хронологический порядок имеет смысл.Сначала покажите событие, которое начинается первым.

Я бы решил проблему с состоянием экрана иначе, не перепаковывая элементы.Например, уменьшите размер элементов, но покажите подсказку с дополнительной информацией, когда пользователь наводит указатель мыши на элемент.Когда пользователь выбирает элемент (щелчком мыши), отображается полная информация.

Answer 2

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

А так как диапазон абсцисс фиксирован входными условиями, вам нужно только найти диапазон ординат?

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