6.2 Планирование

Многие задачи на составление расписания решаются с помощью жадных алгоритмов. Рассмотрим классическую задачу:

Дано n событий с моментами начала и конца. Нужно выбрать как можно больше событий так, чтобы никакие два выбранных события не пересекались.

Выбирать событие частично нельзя.

Например, пусть есть такие события:

Событие	Начало	Конец
A	1	4
B	3	5
C	4	10
D	6	8

В этом случае максимум — 2 события. Например, можно выбрать B и D.

Пример допустимого расписания

Время: 1 2 3 4 5 6 7 8 9 10
A    : [1---4]
B    :     [3-5]
C    :       [4---------10]
D    :           [6-8]

Один из оптимальных выборов: B, D

Возникает вопрос: какую жадную стратегию выбрать, чтобы она работала всегда?

Алгоритм 1

Первая идея — всегда брать самое короткое из доступных событий.

На приведённом выше примере такая стратегия действительно может дать оптимальный ответ. Но в общем случае она неверна.

Рассмотрим контрпример:

Событие	Начало	Конец
A	1	4
B	4	7
C	3	5

Если выбрать самое короткое событие C, то потом уже нельзя взять ни A, ни B, и получится только 1 событие.

Но оптимально выбрать A и B, и тогда получится 2 события.

Значит, стратегия «брать самое короткое» не подходит.

Алгоритм 2

Другая идея — всегда брать следующее возможное событие, которое начинается раньше всех.

Эта стратегия тоже выглядит естественно, но и она может ошибаться.

Контрпример:

Событие	Начало	Конец
A	1	9
B	2	4
C	5	7

Если выбрать событие A, потому что оно начинается раньше всех, то больше взять ничего не получится.

Но если выбрать B, а затем C, то можно включить в расписание 2 события.

Значит, стратегия «брать то, что начинается раньше» тоже неверна.

Алгоритм 3

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

Именно эта стратегия всегда даёт оптимальный ответ.

На интуитивном уровне причина такая:

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

Иначе говоря, такой выбор меньше всего «загромождает» будущее расписание.

Почему это правильно

Пусть мы выбираем первое событие. Сравним два варианта:

• событие X, которое заканчивается раньше,
• событие Y, которое заканчивается позже.

Если вместо X взять Y, то после него допустимых продолжений будет не больше, чем после X, потому что Y занимает больше времени вправо по оси.

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

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

Итак, правильный жадный алгоритм такой:

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

Итог

Для задачи выбора максимального числа непересекающихся событий оптимальна жадная стратегия:

всегда выбирать событие, которое заканчивается раньше всех среди подходящих.

Это хороший пример того, что:

• не всякая естественная жадная идея верна;
• для жадного алгоритма важно не только придумать стратегию, но и обосновать, почему локально лучший выбор остаётся лучшим глобально.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<pair<int,int>> events = {
        {1,4}, {3,5}, {4,10}, {6,8}
    };

    sort(events.begin(), events.end(), [](auto a, auto b) {
        if (a.second != b.second) return a.second < b.second;
        return a.first < b.first;
    });

    int ans = 0;
    int last_end = -1;

    for (auto [l, r] : events) {
        if (l >= last_end) {
            ans++;
            last_end = r;
        }
    }

    cout << ans << "\n";
}

Замечание

Если в условии интервалы считаются пересекающимися даже при касании концами, то в проверке нужно использовать строгое сравнение:

• либо l > last_end,
• либо заранее аккуратно договориться, как именно задаются границы интервалов.