Intervals — это интервалы, то есть отрезки / промежутки / диапазоны.
В алгоритмах interval обычно означает пару:
(start, end)
То есть:
(1, 5)
означает промежуток от 1 до 5.
Например:
(1, 5) = от 1 до 5
(7, 10) = от 7 до 10
(12, 15) = от 12 до 15
Это может быть что угодно:
время встречи: с 10:00 до 11:30
занятость комнаты: с 14:00 до 16:00
отрезок на прямой: от x = 3 до x = 8
период аренды: с 1 июня по 15 июня
диапазон чисел: от 20 до 50
позиции в строке: с символа 5 по символ 12
Например, задача:
intervals = [(1, 3), (2, 4), (5, 7)]
Это значит:
первый интервал: от 1 до 3
второй интервал: от 2 до 4
третий интервал: от 5 до 7
Визуально:
1----3
2----4
5----7
Первые два интервала пересекаются:
(1, 3) и (2, 4)
Потому что второй начинается в 2, когда первый ещё не закончился в 3.
Их можно объединить:
(1, 3) + (2, 4) = (1, 4)
Потому что вместе они покрывают весь диапазон от 1 до 4.
А (5, 7) уже отдельно, потому что между 4 и 5 есть разрыв.
Итог:
[(1, 4), (5, 7)]
Самая типовая задача с intervals — merge intervals, то есть “слить пересекающиеся интервалы”.
Например:
intervals = [(5, 7), (1, 3), (2, 4), (8, 10)]
Сначала сортируем по началу интервала:
[(1, 3), (2, 4), (5, 7), (8, 10)]
Потом идём слева направо и смотрим:
(1, 3) и (2, 4) пересекаются → объединяем в (1, 4)
(5, 7) не пересекается с (1, 4) → оставляем отдельно
(8, 10) не пересекается с (5, 7) → оставляем отдельно
Получаем:
[(1, 4), (5, 7), (8, 10)]
Главная проверка пересечения такая:
if current_start <= previous_end:
Например:
previous = (1, 3)
current = (2, 4)
current_start = 2
previous_end = 3
2 <= 3 → пересекаются
А вот так:
previous = (1, 4)
current = (5, 7)
current_start = 5
previous_end = 4
5 <= 4 → нет, не пересекаются
То есть intervals — это просто способ представить куски чего-то: времени, числовой прямой, координат, диапазонов. А sorting + scan тут нужен потому, что после сортировки интервалы идут по порядку, и тебе достаточно сравнивать текущий интервал только с последним объединённым, а не со всеми подряд.
