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

[avva]

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

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

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

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

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

Comments

[dimrub.livejournal.com]

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

[dimrub.livejournal.com]

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

[dimrub.livejournal.com]

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

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

[avva.livejournal.com]

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

Я не написал свою версию - я думал над задачей минут 20-30, ничего кроме совсем гиблого перебора не придумал, и посмотрел решение.