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

[avva]

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

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

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

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

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

Comments

[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 - и так методом бисекции находим искомое время.

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

[hlodvig.livejournal.com]

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

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