Жадный выбор: доказываем, когда локальное решение достаточно

В одной аудитории нужно провести как можно больше встреч. Каждая занимает интервал времени, встречи нельзя разрывать или переносить. Можно пытаться выбрать самую короткую встречу, самую раннюю по началу или самую раннюю по окончанию. Только интуиция не показывает, какое правило даст максимум.

Записываем точный договор

Интервал обозначим [start,end): он включает начало и исключает конец. Поэтому встреча, начинающаяся ровно при окончании предыдущей, допустима. start должен быть строго меньше end. Все встречи имеют одинаковую ценность 1; цель — максимальное количество, не суммарная длительность и не доход.

Неверный договор делает правильный алгоритм бесполезным. Если комнаты две, встречи имеют веса или допускается прерывание, это другие задачи. Нельзя переносить доказательство без проверки условий.

Выбор раннего окончания

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

sort.Slice(intervals, func(i, j int) bool {
    return intervals[i].End < intervals[j].End
})
selected := []Interval{}
for _, current := range intervals {
    if len(selected) == 0 || current.Start >= selected[len(selected)-1].End {
        selected = append(selected, current)
    }
}

Если договор требует сохранить вход, сначала копируйте intervals. Эталон MaxNonOverlapping также задаёт вторичное сравнение Start при одинаковом End. Оно делает выбор воспроизводимым, но не является причиной оптимальности числа встреч.

Обменное доказательство

Возьмём какое-нибудь оптимальное расписание и его первую встречу o. Пусть g — встреча с самым ранним окончанием среди всех. Окончание g не позже окончания o. Заменим o на g: остальные встречи оптимального расписания начинаются после окончания o, поэтому после g они тоже допустимы. Число встреч не уменьшилось.

Значит существует оптимальное решение, начинающееся с нашего выбора. После g остаётся такая же задача на встречах, начинающихся после его окончания. Повторение аргумента обосновывает все последующие выборы. Мы не доказали, что жадность всегда хороша; мы доказали одно конкретное правило при данном договоре.

Контрпримеры помогают выбрать доказательство

Правило самого раннего начала выберет длинную встречу 0..10 вместо трёх 1..2,2..3,3..4. Самая короткая встреча тоже не универсальна: интервалы 0..3,3..6 и 2..4; середина 2..4 короче первых двух, но перекрывает обе. Оптимальный ответ — первые две.

Для взвешенных встреч раннее окончание может выбрать много дешёвых встреч вместо одной дорогой. Обычно требуется динамическое программирование по отсортированным окончаниям и предшествующей совместимой встрече. Признак смены метода — изменившаяся цель, а не личное предпочтение автора.

Стоимость

Сортировка требует O(n log n), проход — O(n). Копия входа и список ответа используют O(n) памяти. Если интервалы уже отсортированы по End, можно выполнить только линейный проход; это предусловие должно быть явным. Прятать сортировку внутри функции и объявлять O(n) неверно.

Самостоятельная практика

Напишите MaxNonOverlapping и проверки договора. Для {0,3},{3,6},{2,4} ожидайте две совместимые встречи. Добавьте отрицательные моменты времени, равные окончания, касание границ, пустой вход и перевёрнутый интервал.

Для n≤12 переберите все подмножества, проверьте совместимость и сравните максимальное количество с жадным результатом. Этот медленный эталон специально не использует то же правило выбора. Сравнивайте число и допустимость, а не одну точную последовательность при нескольких оптимумах. Практика — 55 минут.

Критерии готовности: полуоткрытые границы объяснены; цель не перепутана с весом; обменное доказательство изложено своими словами; вход не меняется при таком договоре; каждый выбранный интервал допустим.

Разбор

Встречи 0..3 и 3..6 совместимы. Проверка Start > previous.End ошибочно исключит вторую. Перебор подмножеств на небольших входах укрепляет проверку реализации, но не заменяет доказательство для произвольного n.

Источники: MIT 6.006: материалы и задачи, Princeton: sorting applications. Задача и обменный разбор здесь написаны для этого курса.