задачка (программирование)

[avva]

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

Вы - авиадиспетчер, которому нужно посадить N самолетов в аэропорту, у которого только одна посадочная полоса. Про каждый самолет известно окно времени, в которое он может безопасно приземлиться - оно задается в минутах, от 0 до 1440. Например, про один самолет может быть известно, что его можно посадить в любое время от 7-й минуты до 300-й включительно, про другой - в любое время от 100-й до 200-й, и так далее. Предположим, что вы для каждого самолета выбрали время посадки (его можно задать с точностью до секунды). Будет какое-то минимальное временное расстояние между посадками самолетов. Ваша задача -- это минимальное расстояние максимизировать.

На вход вам дается: число самолетов N, от 2 до 8; для каждого самолета начальная и конечная границы окна, от 0 до 1440. На выход вы должны дать: максимальное значение минимального расстояния между посадками, которое вы беретесь обеспечить.

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

P.S. Я бы сказал, опираясь на собственный опыт, что эта задача несколько сложнее, чем типичная алгоритмическая задача на интервью в Гугле. Если вы можете эту задачу решить и за 45 минут написать работающий код, за разумное время дающий правильный ответ - ваш уровень по крайней мере в алгоритмах вполне подходит и даже превосходит то, что в Гугле просят продемонстрировать на интервью.

Comments

[mikhail edoshin (from livejournal.com)]

это не UVa Online Judge? Если да, то подскажите, пожалуйста, номер задачи.

[dimrub.livejournal.com]

Прикольная задача. Первые мысли такие: рассмотрим сначала случай без overlaps (вполне возможно, что это лишнее ограничение). Я подумываю об итеративном алгоритме, который выглядит следующим образом. Сначала мы ставим каждый самолет в середину его интервала. Далее мы находим минимальный интервал между самолетами, и начинаем его раздвигать вправо и влево с одинаковой скоростью, пока он не сравняется с одним из соседних, либо пока один из самолетов не дойдет до конца своего интервала. Теперь находим новый минимальный интервал. Если его нет (все интервалы равны) - мы дошли до оптимума, похлопаем себя по плечу. Если же есть - пытаемся раздвинуть теперь уже его. Если не раздвигается - процесс завершился, опять же, мы дошли до оптимума (как доказать, что этот оптимум глобальный - пока непонятно), прекращаем. В общем, думаю дальше.

[lightjedi.livejournal.com]

FindMaxMinGap
Вход: (N окон, Start time, End Time)

Для всех самолетов А из N
- выбрать А первым самолетом в расписании посадок
- Назначить ему время посадки T_A - самое раннее из возможных
- Найти такое T', что
(Уравнение 1): (T'-T_A) = FindMaxMinGap(N-1 оставшихся окон, T', End Time)
(если такого нет, то наибольшее T', для которого левая часть меньше правой)
- вернуть (T'-T_A)

Если N=1, вернуть T_E - Start_time, где T_E = самое позднее время посадки данного самолета.

Ключевой момент - поиск T'. Здесь мы замечаем, что FindMaxMinGap - невозрастающая функция от второго параметра (Start Time), поэтому решение уравнения (1) можно провести бинарным поиском - т.е. порядка 16 попыток для 86400 возможных позиций. Итого сложность будет где-то 16^N * (N!).

[dimrub.livejournal.com]

Поправка: не надо интервал раздвигать сразу и вправо и влево (это муторно). Можно его сдвинуть либо вправо, либо влево, пока он не сравняется с соседним (это просто: допустим, мы решаем попробовать расширить минимальный интервал влево. Берем левый самолет нашего интервала и сдвигаем его влево так, чтобы либо текущий интервал сравнялся с тем, что слева, либо левый самолет уткнулся в свою границу. Если же после этого нынешний интервал все еще является самым маленьким, то теперь сдвигаем его правый самолет вправо).

[megamihalych.livejournal.com]

Все границы окон упорядочить по возрастанию.
первый самолет посадить в минимальную границу, последний - в максимальную.
Остальные самолеты первоначально расположить произвольно. Затем рассчитать попарные расстояния между соседними. понятно, что расстояния между не-соседними можно не принимать во внимание. после этого начать усреднять эти расстояния. В качестве начальной пары можно взять минимальное и усреднить с бОльшим из соседей. Далее цикл повторяется. Если новое значение оказывается за пределами окна для данного самолета - оставить на ближайшей к этому значению границе.
Поннятно, что при таком алгоритме минимальное расстояние не уменьшается, и ограницено сверху значением 1440/(N-1), поэтому имеет предел. Установить порог изменения в 1 секунду, после чего цикл обрывать при изменениях меньше секунды.

Насчет скорости сходимости алгоритма - надо подумать, сходу кажется, что количество операций - полином от N.

[resolvent.net (from livejournal.com)]

Перебираем все перестановки самолетов (N!).

Делением пополам перебираем размеры минимального расстояния (log(1440/(N-1)).

Пытаемся расставить самолеты с заданным минимальным расстоянием и в заданном порядке (легко сделать за один проход).

Итого: O(N*N!*log(1440/(N-1))) - при ограничении на N <= 8 должно давать разумное время.

[lifewalker.livejournal.com]

Люблю дискретную оптимизацию!

[hlodvig.livejournal.com]

А что будет, если у первого самолета допустимое окно 7-300 минуты, а у второго окно 8-9 минуты?

[dimrub.livejournal.com]

Чтобы не быть голословным: http://codepad.org/NnNDLURf
Тут явно какие-то end cases по углам прячутся, лень было их искать (на интервью я бы постарался :)), плюс это только non-overlapping case.

А ты свой вариант написал?

[hlodvig.livejournal.com]

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

[avva.livejournal.com]

Нет, задача не зациклена, есть только один день.

[dimrub.livejournal.com]

...в конце которого солнце взрывается?

[hlodvig.livejournal.com]

Навскидку алгоритм какой-то сложный. Дабы учесть все возможные случаи оверлаппинга придется делать цикл сначала по возрастанию от первого к последнему, потом второй цикл от последнего к первому.
Суть:
1. сортируем самолеты по началу окна - получаем arr
2. для каждого элемента arr считаем delta_max - max из окна между прилетом arr[i] и arr[i+1]
3. берем минимальное значение из всех delta_max и погнали по массиву arr - для arr[0] берем, конечно же, начало промежутка. для каждого arr[i] если time(arr[i]) попадает в окно времени arr[i+1] - все ок, идем к следующему. если дошли до конца массива и наша delta меньше delta_max, то берем середину между delta и delta_max (с округлением до секунд, конечно же), иначе - делим пополам delta - и так методом бисекции находим искомое время.

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

[megamihalych.livejournal.com]

Вы правы - предложенный мной алгоритм может найти всего-лишь локальный максимум - а нужен глобальный.

Но это легко лечится - если окна пересекаются, то размножаем самолеты:
в каждой области попарного пересечения - будет два самолета (т.е. в вашем примере - 4 самолета - первый в области 7-8, два самолета в области 8-9 и четвертый самолет в области 9-300).
Решаем задачу, населенную размноженными самолетами, а потом вспоминаем, что некоторые из размноженных - один и тот же - после чего перебираем все варианты его помещения в одно положение из всех, которые занимали его клоны.
После чего решаем все переборы по исходному алгоритму, а из множества полученных вариантов выбираем максимальный.
( в вашем примере, оптимальное положение четырех самолетов - в точках 7,8,9,300, после чего решаем четыре задачи:
нач. первого нач. второго
7 8 - конечное положение 7,9 - расстояние 2
7 9 - конечное положение 7,9 - расстояние 2
8 9 - конечное положение 7,9 - расстояние 2
9 8 - конечное положение 8,300 - расстояние 292
300 8 - конечное положение 8,300 - расстояние 292
300 9 - конечное положение 8,300 - расстояние 292

Ответ - 292)

[mike aizatsky (from livejournal.com)]

Навскидку: при заданной перестановке самолетов они себя ведут как линейная система с ограничениями - грузики с пружинками в желобах. Видно как добавление одного шарика меняет систему (или перераспределяет расстояние поровну если может или упирает шарик в стенку). Итого за квадрат в худшем случае можно справиться.

Но вот что с перестановками делать - ума не приложу.

[raydac.livejournal.com]

сажаем сразу все в одно время на одну полосу, процесс снимаем на мобилу и выкладываем на ютюб, миллионы просмотров гарантированы

[timur0.livejournal.com]

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

[hlodvig.livejournal.com]

хреновый алгоритм. если самолеты прилетают в окнах 1-13, 2-4, 5-7, то понятно, что максимальное окно, которое мы можем обеспечить - это 5. Но первым прогоном (с начала по сортированному массиву по началам) мы получим 3. Вторым прогоном (с конца по сортированному массиву по началам) мы получим 5. Третьим прогоном (с начала по сортированному массиву по концам) мы получим 5. Четвертым прогоном (с конца по сортированному массиву по концам) мы получим снова 5. Т.е все же нужно рассматривать все 4 прогона и брать максимальное из результатов?

Должен быть проще алгоритм.

[rusquant.livejournal.com]

это задача линейного программирования размерности ~N^2/2, т.е. вполне разумной. симплекс-метод или interior-point солвер можно конечно написать за 45 минут, но зачем?

[moon-aka-sun.livejournal.com]

Уточним: Вероятно, окно может быть и от 1400 до 100?

[rotozeеv (from livejournal.com)]

А в таких задачах нужно доказывать, что алгоритм приведет к оптимальному решению? А то у меня есть простая идея:

Ставим все времена на левые края окон.
Берем 1 самолет и двигаем его по его интервалу - если какое то новое положение 1го самолета дает общий выигрыш, то оставляем его.
Берем 2 самолет и двигаем ...
...
Берем N самолет и двигаем...
И снова берем 1 самолет ...

Продолжать, пока не получим, что ни один из N самолетов нельзя переставить не ухудшив результат.

[avva.livejournal.com]

Нет, есть только один день и все промежутки внутри [0,1400].

[mkal.livejournal.com]

Лично я бы не стал много думать и просто решил N! раз задачу линейного программирования.

[http://users.livejournal.com/_sabiko/]

В порядке бреда - на уровне простого школьника:

- Ищем min левых границ и max правых, этот диапазон разбиваем на равные N-1 частей - получаем "идеальные" точки
- Смотрим, диапазоны, не покрывающие ни одной, ищем среди них минимальное расстояние от границы диапазона до одной из точек, сдвигаем её на границу диапазона, отрезки по обе стороны переразбиваем, диапазон и точку убираем из рассмотрения
- Смотрим точки, не покрытые ни одним диапазоном, та же процедура
- Все диапазоны покрывают хотя бы одну точку и каждая покрыта хотя бы одним диапазоном - можно распределить без дальнейших сдвигов времени вылетов - не будем этого делать, просто смотрим минимум, это результат

В каком случае такой подход ломается?

[huzhepidarasa.livejournal.com]

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