Алгоритмы с нуля
Планирование интервалов: выбор активностей и слияние интервалов
У тебя одна переговорная и стопка заявок на встречи, у каждой есть время начала и конца. Многие из них конфликтуют. Ты не можешь вместить их все, так что ты хочешь вместить максимум возможного. Чутьё говорит: хватай встречу что начинается раньше всех, потом следующую что вмещается, и так далее. Это чутьё неверно, и оно неверно так что стоит тебе встреч. Правильный ход почти противоположен — заботься о том когда каждая встреча заканчивается, а не когда начинается. Одна сортировка, один проход, доказуемо оптимально. Этот урок учит этот жадный, его близкого родственника «слей пересекающиеся интервалы», и вариант с подсчётом комнат — три задачи которые встречаются постоянно и все живут или умирают от того по чему ты сортируешь.
После этого урока ты можешь решить три классические интервальные задачи. (1) Выбор активностей / максимизация планирования интервалов: выбери наибольшее множество непересекающихся интервалов сортируя по раннему времени завершения и жадно беря каждый интервал чьё начало в момент или после завершения последнего взятого интервала. Ты можешь объяснить почему время завершения это правильный ключ и привести конкретный контрпример показывающий что сортировка по времени начала или по кратчайшей длительности проваливается. (2) Слияние интервалов: сверни множество интервалов в минимальное множество непересекающихся сортируя по началу и проходя, расширяя текущую серию пока следующий интервал пересекает её. (3) Минимум комнат («meeting rooms II»): найди пиковое число одновременно активных интервалов сортируя времена начала и времена конца отдельно и проходя счётчиком с двумя указателями. Ты можешь сформулировать что все три это O(n log n), доминируемые сортировкой, с O(n) или O(1) дополнительной работой в проходе. Ты связываешь это обратно с аргументом обмена из урока 02: раннее завершение доказуемо оптимально потому что любое оптимальное решение может быть переписано чтобы начинаться с самого рано завершающегося интервала без потери счёта.
Задача 1: выбери максимум непересекающихся интервалов
Тебе даны интервалы вроде [start, end]. Два интервала пересекаются если один начинается раньше чем другой заканчивается. Ты хочешь наибольшее множество без пересечений. (Думай: максимум встреч которые ты можешь вместить в одну комнату, максимум задач которые одна машина может выполнить.)
Выигрышный жадный это одна строка интуиции: сортируй по времени завершения, потом иди слева направо беря любой интервал что начинается в момент или после того как закончился последний взятый.
sorted by finish: [1,4] [3,5] [2,6] [5,7] [6,8]
====
take [1,4] ---- lastEnd = 4
[3,5] starts 3 < 4 skip (overlaps)
[2,6] starts 2 < 4 skip (overlaps)
[5,7] starts 5 >= 4 take, lastEnd = 7
[6,8] starts 6 < 7 skip (overlaps)
result: { [1,4], [5,7] } -> 2 intervalsПочему время завершения? Интервал что заканчивается раньше всех оставляет за собой больше всего места для всего остального. Взять его никогда не может тебе навредить: какое бы оптимальное решение ни существовало, ты можешь обменять его первый интервал на самый рано завершающийся без создания нового пересечения и без потери счёта. Это ровно аргумент обмена из урока 02 — выбор раннего завершения «безопасен», так что жадно повторять его оптимально.
Соблазнительные неверные жадные
- Сортировка по времени начала. Встреча что начинается в 9:00 и идёт весь день будет схвачена первой и заблокирует всё. Раннее начало ничего не говорит о том сколько места осталось.
- Сортировка по кратчайшей длительности. Это кажется умным — маленькие встречи должны паковаться плотно — но один короткий интервал может сесть прямо посередине и заблокировать два более длинных которые друг друга не пересекали. Контрпример:
[0,4],[3,5],[4,8]. Самый короткий это[3,5](длина 2). Возьми его и оба[0,4]и[4,8]теперь конфликтуют с ним, так что ты получаешь 1. Но[0,4]и[4,8]друг друга не пересекают, так что настоящий ответ это 2. Раннее завершение берёт[0,4](заканчивается в 4), потом[4,8](начинается в 4) и получает 2. Кратчайшая длительность проигрывает.
Урок: с интервалами правильная вещь по которой сортировать редко очевидная вещь. Время завершения выигрывает для максимизации.
Задача 2: слей пересекающиеся интервалы
Другая цель: дано пересекающиеся интервалы, сверни их в наименьшее число непересекающихся интервалов которые покрывают ту же область. [1,3], [2,6], [8,10], [15,18] становится [1,6], [8,10], [15,18].
Здесь ты сортируешь по времени начала и проходишь:
sorted by start: [1,3] [2,6] [8,10] [15,18]
current run = [1,3]
[2,6]: 2 <= 3 (overlaps) -> extend run to [1,6]
[8,10]: 8 > 6 (gap) -> close [1,6], open new run [8,10]
[15,18]: 15 > 10 (gap) -> close [8,10], open new run [15,18]
result: [1,6] [8,10] [15,18]Сортировка по началу гарантирует что как только ты прошёл интервал, ничто позже не может дотянуться назад за начало текущей серии, так что ты всегда сравниваешь только против одной серии которую сейчас строишь. Это то что делает один проход слева направо корректным.
Задача 3: минимальное число комнат («meeting rooms II»)
Теперь у тебя неограниченное время но ты хочешь наименьшее число комнат так чтобы никакие две встречи не делили комнату. Ответ это максимальное число встреч активных в один момент — пиковое пересечение.
Отсортируй все времена начала и все времена конца в два отдельных списка, потом проходи оба счётчиком с двумя указателями: каждый раз когда следующее событие это начало, встреча начинается, так что добавь комнату и отслеживай пик; каждый раз когда следующее событие это конец, встреча закончилась, так что освободи комнату.
starts: 0 5 15 ends: 10 20 30
start 0 -> rooms 1 (peak 1)
start 5 -> rooms 2 (peak 2) [0,30] and [5,10] both active
end 10 -> rooms 1
start 15 -> rooms 2 (peak 2)
...
answer = peak = 2Все три задачи одной формы: сортируй интервалы по правильному ключу, потом сделай один проход. Сортировка это дорогая часть.
Выбор активностей: сортируй по раннему завершению, потом бери что вмещается
Состояние которое надо нести это одно число: lastEnd, время завершения самого недавнего интервала который ты взял. Интервал берётся ровно тогда когда его начало в момент или после lastEnd.
1
function maxActivities(intervals) {
2
// Sort by earliest FINISH time - the safe greedy key
3
const sorted = [...intervals].sort((a, b) => a[1] - b[1]);
4
let count = 0;
5
let lastEnd = -Infinity; // nothing taken yet
6
const chosen = [];
7
for (const [start, end] of sorted) {
8
if (start >= lastEnd) { // starts after the last taken one finishes
9
count++;
10
lastEnd = end; // this interval is now the latest taken
11
chosen.push([start, end]);
12
}
13
}
14
return { count, chosen };
15
}
- L3 Сортируй по индексу 1 (время конца). Эта одна строка это то что делает весь жадный оптимальным.
- L5 lastEnd начинается с -Infinity так чтобы самый первый интервал всегда проходил проверку.
- L8 Жадная проверка: интервал вмещается если он начинается в момент или после последнего завершения. '>=' допускает встык касающиеся интервалы вроде [1,4] потом [4,8].
- L10 Зафиксируй этот интервал: увеличь счёт и продвинь lastEnd до его завершения.
- L11 Запиши его (опционально — убери 'chosen' если тебе нужен только счёт).
Запуск
Одиннадцать активностей; жадный находит четыре что никогда не пересекаются.
Жадный по кратчайшей длительности неверен — доказательство контрпримером
Запусти неверную стратегию против правильной на ловушке-входе [0,4], [3,5], [4,8]. Самый короткий интервал [3,5] сидит посередине и блокирует оба других.
Двое против одного. Самый короткий интервал выглядел безобидным и стоил целого слота. Время завершения это единственный ключ который доказуемо безопасен.
Слияние интервалов: сортируй по началу, проходи, расширяй текущую серию
Заметь Math.max(last[1], end) на строке расширения: без него полностью вложенный интервал вроде [2,3] внутри [1,4] ошибочно сжал бы серию до [1,3]. Случай «nested» доказывает что защита работает — серия остаётся [1,4].
Давай протрассируем выбор активностей на [[3,5], [1,4], [5,7], [2,6], [6,8]] (намеренно неотсортированном, так чтобы шаг сортировки был виден). Жадный держит один кусок состояния, lastEnd, и вердикт это «бери» когда start >= lastEnd.
1
const sorted = intervals.sort((a, b) => a[1] - b[1]);
2
let lastEnd = -Infinity;
3
for (const [start, end] of sorted) {
4
if (start >= lastEnd) {
5
take(start, end); lastEnd = end;
6
}
7
}
Время: O(n log n) — доминирует сортировка
У каждого из трёх алгоритмов одинаковая разбивка стоимости:
sort the n intervals O(n log n) <- the expensive step
one linear sweep O(n)
total O(n log n)Жадный проход сам по себе это один проход: каждый интервал смотрится один раз, с O(1) работой (сравнение и может быть обновление). Это O(n). Единственная причина почему вся вещь не O(n) это сортировка, которая O(n log n). Так для всех трёх:
activity selection O(n log n) (sort by finish)
merge intervals O(n log n) (sort by start)
minimum rooms O(n log n) (sort starts and ends)Это подпись интервальных жадных: сортировка это вся стоимость алгоритма. Если интервалы приходят уже отсортированными по нужному ключу (иногда верно для потоков событий), один проход это O(n).
Память: O(n) или O(1) помимо сортировки
- Выбор активностей нуждается только в
lastEndи счётчике: O(1) дополнительно (O(n) если ты также собираешь список выбранных). - Слияние интервалов строит выходной список, который не более n интервалов: O(n).
- Минимум комнат держит два отсортированных массива времён начала/конца: O(n).
Сортировка может использовать от O(log n) до O(n) вспомогательной памяти в зависимости от реализации, но доминирующая история такая: дешёвый проход, одна сортировка, O(n log n) время.
Чтобы выбрать максимальное число непересекающихся интервалов, по чему ты должен сортировать?
Почему 'сортировка по кратчайшей длительности' это неверный жадный для максимизации непересекающихся интервалов?
Для слияния пересекающихся интервалов в наименьшее число непересекающихся, какой правильный подход?
Ответ 'минимального числа комнат' (meeting rooms II) равен какой величине?
Почему все три интервальных алгоритма O(n log n)?
Дано интервалы [1,4], [2,5], [7,9], какое минимальное число комнат нужно (пиковое пересечение)?
Дано интервалы [0,2], [1,3], [2,4], [3,5], сколько непересекающихся интервалов ты можешь выбрать максимум?
Частая ошибка
Ошибка: сортировка по времени начала для задачи максимизации. Сортировка-по-началу верна для слияния интервалов, так что легко тянуться к ней везде. Но для выбора максимума непересекающихся интервалов она проваливается: встреча что начинается раньше всех но идёт вечно хватается первой и блокирует всё после неё. Ключи специфичны для задачи — время завершения для максимизации, время начала для слияния. Перепутать их тихо возвращает неверный-но-правдоподобный ответ.
Граничные случаи
Касающиеся концы: [1,4] потом [4,8] это пересечение? Это зависит от того полуоткрыты ли интервалы. В большинстве задач планирования они да: встреча заканчивающаяся в 4:00 и одна начинающаяся в 4:00 не конфликтуют, так что проверка это start >= lastEnd (используй >=, допуская встык). Если концы включающие и касание считается конфликтом, используй start > lastEnd. Для слияния интервалов тот же выбор появляется: start <= last[1] сливает касающиеся интервалы в одну серию; start < last[1] держит их раздельно. Реши соглашение о концах сначала, потом выбери >/>= соответственно — одно неверное сравнение сдвигает каждый ответ на единицу.
Почему это работает
Почему раннее завершение доказуемо оптимально? Это аргумент обмена из урока 02. Предположим какое-то оптимальное решение не начинается с самого рано завершающегося интервала f. Его первый интервал g заканчивается не раньше чем f (так как f заканчивается раньше всех). Обменяй g на f: потому что f заканчивается в момент или раньше чем g, f не может пересекать ничего что шло после g, так что обмен остаётся валидным и держит тот же счёт. Повторяя аргумент, ты можешь перестроить любое оптимальное решение чтобы оно начиналось с выбора жадного. Жадный выбор поэтому «безопасен», а последовательность безопасных выборов оптимальна. Это сердце того почему жадный работает здесь и не для, скажем, размена монет с произвольными номиналами.
Ещё практика
Чеклист интервального жадного. (1) Что ты оптимизируешь — максимум интервалов, минимум слитых серий, минимум комнат? (2) Выбери ключ сортировки: время завершения для «максимум непересекающихся», время начала для «слияние», списки начал-и-концов для «минимум комнат». (3) Неси минимальное состояние: lastEnd для выбора, текущую серию для слияния, текущий счётчик и пик для комнат. (4) Один проход, O(1) работы на интервал. (5) Реши соглашение о концах (> против >=) заранее. Стоимость всегда O(n log n), и почти вся она это сортировка.
Опиши как максимизировать число непересекающихся интервалов, почему этот жадный корректен, чем он отличается от слияния интервалов, и сложность этих интервальных алгоритмов.
Три интервальные задачи, все решаемые сортируй по правильному ключу, потом один проход.
Выбор активностей (максимум непересекающихся интервалов): сортируй по раннему времени завершения, бери каждый интервал чьё начало >= lastEnd, продвигай lastEnd. Корректно по аргументу обмена: самый рано завершающийся интервал всегда безопасный выбор потому что он оставляет за собой больше всего места.
Неверные жадные которых надо избегать: сортировка-по-началу (ранний-но-длинный интервал блокирует всё) и сортировка-по-кратчайшей-длительности (короткий интервал посередине блокирует двух непересекающихся соседей — [0,4],[3,5],[4,8] даёт 1 вместо 2).
Слияние интервалов (наименьшее число непересекающихся серий): сортируй по началу, проходи, расширяй текущую серию пока start <= last[1] (используй Math.max на конце чтобы пережить вложенные интервалы), иначе открой новую серию.
Минимум комнат (meeting rooms II): ответ это пиковое пересечение. Сортируй начала и концы отдельно, проходи счётчиком с двумя указателями — добавляй комнату на каждое начало, освобождай одну на каждый конец, отслеживай максимум.
Сложность: все три это O(n log n), с сортировкой доминирующей O(n) проход. Память это O(1) (выбор, только счёт) до O(n) (выход слияния, массивы комнат). Соглашение о концах (> против >=, < против <=) решает считаются ли касающиеся интервалы пересекающимися — выбери его до того как напишешь сравнение.
Повторяющийся урок интервальных жадных: сложная часть это выбор того по чему сортировать, а не проход. Сделай ключ правильным и остальное это один линейный проход.