Интервалы: покрытие и расписание на Python: как решать + 9 задач с проверкой

Интервалы — это отрезки на прямой или промежутки времени вида [l, r]: фонарь светит на кусок дороги, ремонт перекрывает участок, док занят с t1 до t2, доклад идёт в аудитории с a до b. В олимпиадных задачах чаще всего просят покрыть весь отрезок минимальным числом интервалов или составить расписание: выбрать максимум непересекающихся событий, проверить конфликты, посчитать минимальное число кабинетов/причалов.

Как понять, что это «интервалы: покрытие и расписание»:

• в условии много пар l_i r_i или start end, и важно сравнивать «кто раньше начинается/заканчивается»;
• просят: «покрыть [0, L]», «минимум объектов», «можно ли закрыть все дыры», «максимум мероприятий без пересечений», «минимум ресурсов (аудиторий)»;
• решения в лоб по всем точкам невозможны: координаты до 1e9, а n большое.

Суть приёма: мы сортируем интервалы и дальше идём жадно или «сканируем» события. Для покрытия обычно держим текущую покрытую границу и среди всех интервалов, которые начинаются не правее неё, берём тот, у которого самый дальний правый конец — так делаем минимум шагов. Для расписаний часто сортируют по времени окончания (чтобы набрать максимум непересекающихся) или делают «линейный проход» по событиям начала/конца (чтобы найти пиковое число одновременно идущих дел). Это ускоряет решение до O(n log n) вместо перебора всех сочетаний.

С чего начать учиться:

• потренируйтесь уверенно сортировать интервалы по l, по r, и по паре ключей;
• разберите два жадных шаблона: «покрыть отрезок минимумом» и «выбрать максимум непересекающихся»;
• освоить «события»: для каждого интервала добавить (+1 в начале, -1 в конце) и пройти по отсортированным точкам;
• внимательно оговорить границы: включены ли концы, можно ли касаться (r == l), что считать пересечением.

Ниже — задачи с автопроверкой и разбором подхода по теме интервалов.