Что спрашивают

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

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

Приём решения

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

Преобразуем пары в (end = start + length, start) и отсортируем по end. Массив prefix[j] хранит максимум совместимых заявок среди первых j участков. Для текущего участка найдём j — число уже просмотренных концов, не больших его начала. Это bisect_right(ends, start, 0, i).

Если завершить выбор текущим участком, получится count = prefix[j] + 1. В новый элемент prefix запишем максимум старого значения и count. Отдельно сравним пару (count, end) с лучшей: больший конец при том же количестве уменьшает хвост.

Каждая допустимая последовательность имеет последнюю заявку, и для неё рассмотрен лучший предшествующий набор. Поэтому максимум по всем последним заявкам даёт оба критерия. Время O(N log N), память O(N).

Разбор на примере

Ввод

5
8 30
1 3
2 15
8 2
4 4

Вывод

3 9962
Разбор примера по шагам
Текущий участокЛучший набор с ним последнимЛучшее количество в префиксе
[1; 4]11
[4; 8]22
[8; 10]33
[2; 17]13
[8; 38]3; конец дальше3

Участки [1; 4] и [4; 8] совместимы. После них можно выполнить [8; 10] или [8; 38]. Оба способа дают три заявки, но второй оставляет хвост 10 000 - 38 = 9962. Участок [2; 17] перекрывает первые два и не улучшает количество.

Код на Python и C++

Число j одновременно является индексом prefix: первые j концов совместимы с текущим началом. bisect_right включает равные границе концы.

В C++ вместо bisect_right — upper_bound(ends.begin(), ends.begin() + i, start) - ends.begin(): он даёт то же j.

from bisect import bisect_right
import sys


def solve(requests):
    intervals = sorted((start + length, start) for start, length in requests)
    ends = [end for end, start in intervals]
    prefix = [0]
    best = (0, 0)
    for i, (end, start) in enumerate(intervals):
        j = bisect_right(ends, start, 0, i)
        count = prefix[j] + 1
        prefix.append(max(prefix[-1], count))
        best = max(best, (count, end))
    return best[0], 10000 - best[1]


if __name__ == '__main__':
    data = list(map(int, sys.stdin.buffer.read().split()))
    requests = list(zip(data[1::2], data[2::2]))
    print(*solve(requests))
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> intervals(n);
    for (auto& [end, start] : intervals) {
        int length;
        cin >> start >> length;
        end = start + length;
    }
    sort(intervals.begin(), intervals.end());
    vector<int> ends(n);
    for (int i = 0; i < n; i++)
        ends[i] = intervals[i].first;
    vector<int> prefix = {0};
    pair<int, int> best = {0, 0};
    for (int i = 0; i < n; i++) {
        auto [end, start] = intervals[i];
        int j = upper_bound(ends.begin(), ends.begin() + i, start) - ends.begin();
        int count = prefix[j] + 1;
        prefix.push_back(max(prefix.back(), count));
        best = max(best, {count, end});
    }
    cout << best.first << ' ' << 10000 - best.second << endl;
}

Типичные ошибки

  • Принять длину за координату конца

    Второе число входной строки — длина. Координату конца нужно вычислить как start + length.

  • Запретить касание границ

    Участки с концом, равным началу следующего, совместимы. Нужен bisect_right, а не исключение равенства.

  • Вывести хвост первого жадного набора

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