pattern heroPT–23LeetCode Extension

Интервалы

Сортируем отрезки по началу, и те, что пересекаются, оказываются рядом. Дальше каждый отрезок сравниваем только с предыдущим, а не со всеми остальными.

Вариант
P06 ИнтервалыСлияние · 1×

Пример задачи: слить пересекающиеся интервалы в списке [6, 9], [1, 3], [11, 12], [7, 8], [2, 5], [8, 10].

[1, 3][2, 5][6, 9][7, 8][8, 10][11, 12]итог0123456789101112
ещё впередитекущий интервалпоследний в итогеитогуже учтён

Сортируем по началу: 1, 2, 6, 7, 8, 11

merged = –start = –end = –last = –
01/26
сначала · назад · пуск · шаг
Скорость
1function mergeIntervals(intervals):
2 sort intervals by start
3 merged = [intervals[0]]
4 for each [start, end] after the first:
5 last = last interval in merged
6 if start > last.end:
7 add [start, end] to merged
8 else:
9 last.end = max(last.end, end)
10 return merged

← → шаг · пробел — пауза

Как узнать

список пар [начало, конец], например встреч или бронирований, и вопрос о том, что пересекается.

Как решать такие задачи

  1. Отсортируй по началу. Чтобы оставить как можно больше непересекающихся интервалов, сортируй по концу.
  2. Реши, пересекаются ли интервалы, которые только касаются: начало ≤ последнего конца или начало < последнего конца.
  3. Пройди один раз и сравнивай каждый интервал только с последним сохранённым: продли его или начни новый.
  4. Чтобы узнать, сколько интервалов идёт одновременно, преврати каждый в +1 в начале и −1 в конце, отсортируй эти точки и веди текущую сумму.

Вариант: Сортировка по концу

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

  1. Сортируй по концу, когда жадно выбираешь точки или интервалы и первым должен идти тот, что кончается раньше.
  2. Помни только последний выбор: здесь последний выстрел, конец интервала, ради которого стреляли.
  3. Интервалу, который начинается правее него, нужен новый выбор в его собственном конце. Всё остальное уже покрыто — пропускай.
  4. Чтобы оставить как можно больше непересекающихся интервалов, сортируй так же по концу: бери интервал, если он начинается после конца последнего взятого, остальные выбрасывай.

Где встречается

  • Видео в браузере. Браузер хранит, какие куски видео уже скачаны, как список отрезков времени. Пересекающиеся и соседние отрезки он сливает в один, поэтому список остаётся коротким и упорядоченным.
  • Генетика. bedtools merge склеивает пересекающиеся участки генома. Файл сначала сортируют по началу, а потом каждый участок сравнивают только с предыдущим.
  • PostgreSQL. PostgreSQL умеет хранить диапазоны дат и чисел. Функция range_agg собирает много диапазонов в набор без пересечений, сливая те, что перекрываются.