Сортировка + жадный выбор на интервалах

Интервалы встречаются как встречи в календаре, задания на одном станке, эфирные слоты и бронирования. Здесь важна не длина каждого интервала, а то, сколько места он оставляет следующему.

Как выбрать максимум совместимых встреч

Даны полуинтервалы занятости [start, end). Выбрать максимальное число попарно непересекающихся интервалов. Например, из [1,4), [3,5), [0,6), [5,7), [8,11), [12,16) можно выбрать [1,4), [5,7), [8,11), [12,16).

Что делает перебор всех наборов встреч

Можно перебрать все подмножества из n интервалов, отсортировать выбранные по началу и проверить совместимость. Это до 2^n наборов. Даже рекурсивный выбор «взять или пропустить» порождает экспоненциальное дерево.

Почему варианты расписания пересекаются

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

Почему раннее окончание оставляет больше будущего

Среди ещё доступных интервалов выберем тот, который заканчивается раньше всех. Пусть некоторый оптимальный набор начинается с другого интервала A, а наш выбор — G. Поскольку end(G) <= end(A), можно заменить A на G: все интервалы, шедшие после A, всё ещё начинаются не раньше end(A), значит, не раньше end(G). Размер набора не уменьшился.

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

Что уже гарантирует выбранное расписание

После просмотра первых i интервалов в порядке возрастания end список chosen имеет максимально возможный размер среди совместимых наборов из этого префикса и заканчивается как можно раньше для такого размера. lastEnd — конец последнего выбранного интервала.

Как отбирать встречи по времени окончания

1. Отсортировать интервалы по end, а при равных концах — по start.
2. Установить lastEnd в очень маленькое значение.
3. Идти слева направо. Если start >= lastEnd, взять интервал и присвоить lastEnd = end.
4. Иначе пропустить его: он конфликтует с уже выбранным более ранним окончанием.

Как сохранить границу последней встречи

В коде полуинтервалы считаются совместимыми при next.start >= previous.end: встреча, начинающаяся ровно в момент окончания другой, допустима.

C++17

#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>

using namespace std;

vector<pair<int, int>> selectMeetings(vector<pair<int, int>> meetings) {
    sort(meetings.begin(), meetings.end(), [](const auto& left, const auto& right) {
        if (left.second != right.second) {
            return left.second < right.second;
        }
        return left.first < right.first;
    });

    vector<pair<int, int>> chosen;
    int lastEnd = numeric_limits<int>::min();
    for (const auto& meeting : meetings) {
        if (meeting.first >= lastEnd) {
            chosen.push_back(meeting);
            lastEnd = meeting.second;
        }
    }
    return chosen;
}

int main() {
    vector<pair<int, int>> answer = selectMeetings({{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 11}, {12, 16}});
    vector<pair<int, int>> expected = {{1, 4}, {5, 7}, {8, 11}, {12, 16}};
    assert(answer == expected);
    cout << answer.size() << '\n';
}

Python 3

def select_meetings(meetings: list[tuple[int, int]]) -> list[tuple[int, int]]:
    meetings = sorted(meetings, key=lambda meeting: (meeting[1], meeting[0]))
    chosen: list[tuple[int, int]] = []
    last_end = float("-inf")

    for start, end in meetings:
        if start >= last_end:
            chosen.append((start, end))
            last_end = end
    return chosen


answer = select_meetings([(1, 4), (3, 5), (0, 6), (5, 7), (8, 11), (12, 16)])
assert answer == [(1, 4), (5, 7), (8, 11), (12, 16)]
print(len(answer))

Сколько стоит сортировка расписания

Сортировка занимает O(n log n), один проход — O(n), итог O(n log n). Память — O(n) на отсортированную копию и ответ; при сортировке входа на месте дополнительная память ответа равна O(k). Нужна согласованная модель границ: здесь [a,b) и [b,c) не пересекаются.

Где границы интервалов меняют ответ

Пустой список даёт пустой ответ. Равные окончания: можно взять любой из совместимых кандидатов, но стабильный tie-break делает трассировку предсказуемой. Вложенный интервал часто лучше длинного наружного. Не перепутайте условие с закрытыми интервалами: для [1,2] и [2,3] может требоваться строгое start > lastEnd.

Какие расписания обязаны пройти тест

• [] -> [];
• один интервал;
• касание (1,3), (3,5) — оба выбраны для полуинтервалов;
• полностью вложенные (1,10), (2,3), (3,4) — выбрать два коротких;
• одинаковые концы и интервалы в обратном входном порядке.

Когда в условии искать раннее окончание

Сигналы: «максимум совместимых встреч», «один ресурс», «нельзя пересекаться», «выбрать как можно больше». Если после сортировки решение описывается одной границей lastEnd, проверьте выбор по самому раннему окончанию.

Когда один локальный интервал не решает цель

Не используйте этот выбор, если цель — максимальная суммарная ценность интервалов: там короткий интервал может проигрывать дорогому длинному, и нужен weighted interval scheduling с DP. Не подходит и при нескольких ресурсах без дополнительной структуры данных.

Самопроверка выбора первой встречи

Вопрос: почему после выбора [1,4) можно безопасно отбросить [3,5)?
Ответ: он пересекается с уже выбранным интервалом, а выбранный закончился не позже любого альтернативного первого интервала.

Самопроверка строгих и нестрогих границ

Вопрос: что изменится, если интервалы закрытые [start,end]?
Ответ: касание в точке end становится пересечением, поэтому условие совместимости должно быть start > lastEnd, а не >=.

Потренируйте выбор по окончанию

Отсортируйте [0,2), [1,3), [3,4), [2,5), [4,7) по концу. После каждого кандидата запишите lastEnd и выбранный список. Затем придумайте цены для этих же интервалов, при которых выбор по раннему окончанию перестаёт максимизировать суммарную цену.

Самостоятельное расписание без подсказок

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

Задача 1

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

Что переносить на новые интервалы

В интервальном планировании жадность работает не потому, что короткие встречи «кажутся хорошими», а потому что раннее окончание доминирует над более поздним и допускает обмен с оптимальным решением.