Интервалы и события

В зал подали заявки на мероприятия (1, 3), (3, 5), (5, 8), (9, 15), (12, 16). Как провести как можно больше мероприятий, чтобы они не пересекались?

Каждый раз брать то мероприятие, которое раньше заканчивается: оно раньше освобождает зал.

У мероприятия есть начало и окончание: (start, finish). Пусть следующее мероприятие разрешено начать в момент окончания предыдущего. Тогда мероприятия совместимы, если start следующего ≥ finish предыдущего, а если нужен перерыв P — если start следующего ≥ finish предыдущего + P.

На рисунке видно, как зал освобождается раньше всего и для следующих мероприятий остаётся больше времени:

meetings = [(9, 15), (1, 3), (12, 16), (5, 8), (3, 5)]pause = 0meetings.sort(key=lambda x: (x[1], x[0]))selected = []last_finish = Nonefor start, finish in meetings:    if last_finish is None or start >= last_finish + pause:        selected.append((start, finish))        last_finish = finishprint(len(selected), *selected)

Первый показатель ключа — окончание. Почему первый выбор обрабатывается через None? Чтобы случайно не потребовать перерыв до первого мероприятия: перерыв по условию нужен между мероприятиями.

А почему не брать мероприятие, которое раньше начинается, или самое короткое?

Оба правила ошибаются — это видно на маленьких примерах.

Почему не по началу? Раннее мероприятие может занять весь день:

Почему не по длительности? Короткое мероприятие может пересекаться с двумя длинными:

Значит, нам важно освободиться раньше в абсолютном времени, а не просто выбрать короткое мероприятие.

«Найди наибольшее количество мероприятий и наибольший перерыв между двумя последними». Как учесть второе требование?

Сначала найти наибольшее количество k, оставить первые k − 1 мероприятий жадного расписания и подобрать последнее, которое начинается как можно позже.

Жадный алгоритм выбрал (1, 3), (3, 5), (5, 8), (9, 15) — четыре мероприятия. Но последнее можно заменить на (12, 16): количество останется 4, а перерыв между двумя последними увеличится до 12 − 8 = 4. Порядок решения:

1. Найти максимальное количество k.
2. Взять первые k − 1 мероприятий жадного расписания.
3. Узнать время окончания предпоследнего.
4. Среди допустимых последних мероприятий выбрать то, которое позже начинается.

Почему первые k − 1 можно оставить жадными? Жадное построение позволяет закончить k − 1 мероприятий максимально рано. Более раннее окончание предпоследнего только увеличивает возможный перерыв, а подходящим последним становится любое мероприятие, начинающееся после него. Если гарантировано хотя бы два мероприятия, продолжение программы выше:

penultimate_finish = selected[-2][1]latest_start = Nonefor start, finish in meetings:    if start >= penultimate_finish + pause:        if latest_start is None or start > latest_start:            latest_start = startprint(len(selected), latest_start - penultimate_finish)

selected[-2] — предпоследняя выбранная запись, selected[-2][1] — время её окончания. Обрати внимание: максимизируем начало последнего мероприятия; позднее окончание само по себе не гарантирует большой перерыв. Если мероприятий меньше двух, такого перерыва нет — этот случай определяется условием.

Похожие вопросы решаются той же заменой последнего: самое позднее окончание последнего мероприятия — наибольшее finish среди мероприятий, которые начинаются не раньше penultimate_finish + pause (здесь 16).

Если в файле даны начало и длительность, окончание считают сразу при чтении: finish = start + duration. Если при одинаковом начале нужно выбрать более длительное последнее мероприятие, добавляется ещё один критерий — finish − start; на перерыв он не влияет.

Сервер работал в те же пять интервалов. Сколько времени он работал всего и сколько простаивал?

Объединить пересекающиеся и касающиеся интервалы в непрерывные периоды и сложить их длины; простои — промежутки между периодами.

Это другой вопрос, чем выбор непересекающихся мероприятий. Первые три образуют один непрерывный период (1, 8), последние два — (9, 16). Общая длительность работы (8 − 1) + (16 − 9) = 14.

Сначала сортируем интервалы по началу, затем храним последний уже объединённый интервал:

intervals = [(9, 15), (1, 3), (12, 16), (5, 8), (3, 5)]intervals.sort()merged = []for start, finish in intervals:    if not merged or start > merged[-1][1]:        merged.append([start, finish])    else:        merged[-1][1] = max(merged[-1][1], finish)print(*merged)

Объединённые интервалы записаны списками [start, finish], потому что мы изменяем правую границу: merged[-1][1] = .... Почему используем max? Новый интервал может полностью лежать внутри предыдущего: после (2, 20) и (5, 8) правая граница должна остаться 20. Условие start > merged[-1][1] склеивает касающиеся интервалы: (1, 3) и (3, 5) — один период. Так и нужно, если в момент окончания работа ещё идёт или следующая начинается сразу.

Если нужен суммарный простой за период от 0 до day_end, считаем промежутки между объединёнными интервалами — продолжение программы:

day_end = 18cursor = 0idle_count = idle_duration = 0for start, finish in merged:    if start > cursor:        idle_count += 1        idle_duration += start - cursor    cursor = finishif cursor < day_end:    idle_count += 1    idle_duration += day_end - cursorprint(idle_count, idle_duration)

Учтены простой до первой работы (0–1), простои между работами (8–9) и простой после последней работы (16–18). Здесь предполагается, что все интервалы лежат внутри рассматриваемого периода.

b − a — длительность непрерывного промежутка времени от a до b, а b − a + 1 — количество целых номеров от a до b включительно. От 10:00 до 10:05 прошло 5 минут, а номера 10, 11, 12, 13, 14, 15 — это 6 номеров. Целочисленные значения времени не делают формулу длительности автоматически равной finish - start + 1.

Сколько процессов работало одновременно больше всего и как долго держалась такая нагрузка?

Нагрузка меняется только в моменты начала и окончания — события. Отсортировать события и идти по ним, меняя счётчик.

Проверять каждый момент времени дорого, а событий всего вдвое больше, чем интервалов. Под интервалами — сколько их работает между соседними событиями:

Для модели, в которой объект активен при start ≤ t < finish, записываем в start изменение +1, в finish — изменение -1. Эта модель называется полуинтервалом [start, finish): начало включено, окончание исключено. Изменения копим в словаре через get — в один момент может быть несколько событий:

intervals = [(1, 3), (3, 5), (5, 8), (9, 15), (12, 16)]day_end = 18changes = {0: 0, day_end: 0}for start, finish in intervals:    changes[start] = changes.get(start, 0) + 1    changes[finish] = changes.get(finish, 0) - 1 times = sorted(changes)current = maximum = total_duration = 0for i in range(len(times) - 1):    current += changes[times[i]]    duration = times[i + 1] - times[i]    if current > maximum:        maximum = current        total_duration = duration    elif current == maximum:        total_duration += durationprint(maximum, total_duration)

Сортировка словаря sorted(changes) даёт отсортированный список его ключей. Между двумя соседними моментами количество активных постоянно. Почему сначала меняем current, потом учитываем длительность? Потому что после событий в момент times[i] новое количество действует до следующего события. В момент 3 одно мероприятие заканчивается, другое начинается: общее изменение −1 + 1 = 0, и количество не меняется.

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

А если нагрузку считают только с 8:00 до 14:00 или оба конца интервала включены?

Алгоритм тот же — меняются события: интервалы обрезают краями окна, а при включённом конце событие окончания ставят на минуту позже.

Интервалы, попавшие в окно частично, учитываются, поэтому каждый интервал обрезают краями окна: start = max(start, low), finish = min(finish, high), а если после этого start >= finish, интервал в окно не попал. Если в файле вместо начала или окончания стоит 0 со смыслом «процесс шёл с начала наблюдения» или «не закончился», его заменяют краем окна.

Если время считается целыми моментами и объект активен в оба крайних момента отрезка [start, finish], событие окончания ставят в момент finish + 1: в момент finish объект ещё работает. Сначала определяется смысл времени, затем порядок обработки событий.

Число отрезков, в течение которых количество не менялось, считают по моментам с ненулевым итоговым изменением. Для наших интервалов за период от 0 до 18:

times = [t for t in sorted(changes) if changes[t] != 0]points = [0] + times + [day_end]lengths = [b - a for a, b in zip(points, points[1:])]print(len(lengths), max(lengths), *times)

Моменты 3 и 5 выпали: в них одно мероприятие заканчивается, а другое начинается. Отрезков постоянного количества семь, самый длинный — с 1 до 8.

• Больше всего мероприятийпо раннему окончанию
• Второй критерийпервые k − 1 жадные, последнее — подобрать
• Занятое времяобъединить интервалы, отсортированные по началу
• Нагрузкасобытия +1 и −1, отсортированные по времени
• Включённый конецсобытие окончания в finish + 1
• Окно наблюденияобрезать интервалы краями окна