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

[avva]

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

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

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

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

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

Comments

[mopexod.livejournal.com]

Понятно, что "все пермутации" показались в ответах. Странно, что предлагали другое :)
Еще я не заметил, что самолетов "до 8" - это сразу сводит задачу к "все пермутации и больше ни о чем не думай".
Как решавший эту задачу на практике - выстраивание очереди кораблей к причалу - практически те же условия, как и у самолетов, добавлю, что на практике такое решение не очень годится, если очередь из 20-30.

[migmit.livejournal.com]

А. Блин. Я тоже не заметил.

Тогда, конечно, все перестановки и пошло оно нах.