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

[avva]

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

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

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

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

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

Comments

[mikkim08.livejournal.com]

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

Во-первых, никаких симплекс-методов и т.д. такие задачки не подразумевают. Даже думать в эту сторону не надо.

Во-вторых, ограничение на N от 2 до 8 нам явно говорит о том, что ожидаемое решение подразумевает перебор N! А иначе, почему N такое маленькое ?

И в-третьих, вот это mim max условие максимальное значение минимального расстояния очень напоминает пример FairWorkload отсюда (http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch)

[avva.livejournal.com]

Разумные вещи пишете. Я тоже не отследил важность этого N<=8, когда думал, как и многие другие.

[mikkim08.livejournal.com]

Ограничения это очень важно ! Во всех tutorials на топкодере написано: N < 10 перебор, N < 100 какое-нибудь O(N^3) решение, типа DP и т.д.

А на собеседовании, если ограничение явно не названо, его стоит сразу уточнить.

[mehas.livejournal.com]

Так ведь есть решение(приведенное мной), полиномиальное по N (точнее, за O(Nlog(N)log(T) см. мой коммент). Зачем перебирать все перестановки?

[avva.livejournal.com]

Я не понимаю вашего решения. Если не задать конкретную очередность посадок самолетов, то бинарная функция "достижимо ли время T в качестве ответа" не является монотонной, поэтому бинарный поиск не работает в качестве метода нахождения ответа. Так мне кажется.

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

Но если я неправ, объясните ваше решение подробнее.