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

[avva]

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

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

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

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

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

Comments

[megamihalych.livejournal.com]

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

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

[hlodvig.livejournal.com]

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

[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)