Разбор задачи «День для похода»

Идея задачи

У нас есть N друзей. Для каждого друга известен отрезок дней [A_i, B_i], в которые он занят и не сможет прийти.

Нужно выбрать один день из диапазона [X, Y] так, чтобы свободных друзей оказалось как можно больше.

Другими словами, для каждого дня d из [X, Y] можно посчитать:

• сколько друзей заняты в день d;
• сколько друзей свободны в день d.

Если в день d заняты busy(d) друзей, то свободны:

free(d) = N - busy(d)

Значит, задача сводится к следующей:

Найти день из [X, Y], в который число занятых друзей минимально.

Тогда ответ будет равен:

N - min_busy

Почему нельзя проверять все дни подряд

Наивный подход — перебрать все дни от X до Y и для каждого проверить, сколько друзей заняты.

Но значения X, Y, A_i, B_i могут быть очень большими, вплоть до 10^9. Диапазон [X, Y] тоже может быть очень длинным, поэтому перебор всех дней невозможен.

Нужно решение, которое зависит в первую очередь от N, а не от длины диапазона дней.

Главное наблюдение

Для каждого друга нас интересует только пересечение его занятого отрезка с диапазоном возможной встречи [X, Y].

Пусть у друга отрезок занятости [A_i, B_i].

Тогда внутри допустимого диапазона он занят на отрезке:

• l = max(A_i, X)
• r = min(B_i, Y)

Если l > r, то этот друг вообще не мешает ни в один допустимый день.

Если l <= r, то этот друг увеличивает число занятых на всём отрезке [l, r].

Значит, задача сводится к следующей:

Есть много отрезков на числовой прямой. Нужно найти точку из [X, Y], которая покрыта минимальным количеством отрезков.

Метод событий (разностный массив на координатах)

Когда нужно много раз добавлять +1 на отрезок [l, r], удобно использовать разностный подход:

• в точке l прибавим +1;
• в точке r + 1 прибавим -1.

После этого, если идти слева направо и накапливать сумму, мы будем знать, сколько отрезков покрывают текущую позицию.

Пример

Пусть есть два занятых отрезка:

• [3, 5]
• [4, 7]

Тогда события будут такими:

• в 3: +1
• в 6: -1
• в 4: +1
• в 8: -1

После сортировки событий:

• 3 -> +1
• 4 -> +1
• 6 -> -1
• 8 -> -1

Префиксная сумма даст:

• на дне 3 занят 1 друг,
• на днях 4..5 заняты 2 друга,
• на днях 6..7 занят 1 друг,
• после 8 снова 0.

Именно это нам и нужно.

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

Между двумя соседними точками событий количество занятых не меняется.

Например, если следующее событие происходит в точке pos, а до этого была точка last, то на всём промежутке:

[last, pos - 1]

число занятых одинаково.

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

Это и делает решение быстрым.

Пошаговый алгоритм

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

2. Для каждого друга:

   • найдём пересечение его отрезка занятости с [X, Y];

   • если пересечение непустое, добавим:

     • +1 в точку начала;
     • -1 в точку сразу после конца.
3. Отсортируем все точки событий.
4. Пройдём по ним слева направо, поддерживая текущее число занятых curBusy.
5. Для каждого промежутка между соседними событиями обновим минимум занятых bestBusy.
6. Ответом будет N - bestBusy.

Разбор переменных

• curBusy — сколько друзей заняты на текущем промежутке;
• bestBusy — минимальное число занятых на каком-то допустимом дне;
• last — левая граница текущего промежутка.

Важная тонкость

Мы добавляем событие в r + 1.

Это стандартный приём для работы с включёнными отрезками [l, r].

Почему так?

• на отрезке [l, r] друг занят;
• начиная с дня r + 1 он уже перестаёт быть занятым.

Именно поэтому в r + 1 мы уменьшаем количество активных отрезков на единицу.

Доказательство корректности

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

Лемма 1

Для каждого друга, если его занятость пересекается с [X, Y], то после добавления событий +1 в l и -1 в r + 1 этот друг будет учитываться ровно на всех днях от l до r включительно.

Доказательство. Префиксная сумма увеличивается на 1, начиная с позиции l, и перестаёт включать этот вклад начиная с позиции r + 1. Следовательно, на всех днях l, l + 1, ..., r вклад равен 1, а вне этого диапазона — 0. Лемма доказана.

Лемма 2

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

Доказательство. Количество занятых меняется только в точках, где есть события. Между соседними событиями новых изменений нет, значит значение постоянно. Лемма доказана.

Лемма 3

Алгоритм проверяет все возможные значения числа занятых друзей на днях из [X, Y].

Доказательство. По лемме 2 на каждом промежутке между соседними событиями значение постоянно. Алгоритм рассматривает каждый такой промежуток и обновляет минимум. Значит, минимум по всем дням из [X, Y] будет найден. Лемма доказана.

Теорема

Алгоритм возвращает максимальное количество друзей, которые могут прийти в один выбранный день из [X, Y].

Доказательство. По лемме 3 алгоритм находит минимальное число занятых друзей min_busy среди всех допустимых дней. Тогда максимальное число свободных друзей равно N - min_busy. Именно это и требуется вывести. Теорема доказана.

Оценка сложности

Пусть K — количество различных точек событий. Тогда:

• на каждого друга добавляется не более двух событий;
• значит, K <= 2N.

Итоговая сложность:

• время: O(N log N);
• память: O(N).

Это хорошо подходит для ограничений порядка 10^5.

Эталонная реализация на C++

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int organizza(int N, int X, int Y, vector<int> A, vector<int> B) {
    map<int, int> diff;

    for (int i = 0; i < N; ++i) {
        int l = max(A[i], X);
        int r = min(B[i], Y);

        if (l <= r) {
            diff[l] += 1;
            diff[r + 1] -= 1;
        }
    }

    int curBusy = 0;
    int bestBusy = N;
    int last = X;

    for (auto [pos, delta] : diff) {
        if (pos > Y + 1) {
            break;
        }

        // На промежутке [last, pos - 1] число занятых постоянно и равно curBusy.
        if (last < pos) {
            bestBusy = min(bestBusy, curBusy);
        }

        curBusy += delta;
        last = pos;
    }

    // Если после последнего события ещё остался хвост до Y,
    // то на всём этом промежутке число занятых равно curBusy.
    if (last <= Y) {
        bestBusy = min(bestBusy, curBusy);
    }

    return N - bestBusy;
}

int main() {

    int N, X, Y;
    cin >> N >> X >> Y;

    vector<int> A(N), B(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i];
    }

    cout << organizza(N, X, Y, A, B) << '\n';
    return 0;
}

Эталонная реализация на Python

def organizza(n, x, y, a, b):
    diff = {}

    for i in range(n):
        l = max(a[i], x)
        r = min(b[i], y)

        if l <= r:
            diff[l] = diff.get(l, 0) + 1
            diff[r + 1] = diff.get(r + 1, 0) - 1

    cur_busy = 0
    best_busy = n
    last = x

    for pos in sorted(diff):
        if pos > y + 1:
            break

        # На промежутке [last, pos - 1] число занятых равно cur_busy.
        if last < pos:
            best_busy = min(best_busy, cur_busy)

        cur_busy += diff[pos]
        last = pos

    # Хвост после последнего события
    if last <= y:
        best_busy = min(best_busy, cur_busy)

    return n - best_busy


def main():
    n, x, y = map(int, input().split())

    a = []
    b = []
    for _ in range(n):
        l, r = map(int, input().split())
        a.append(l)
        b.append(r)

    print(organizza(n, x, y, a, b))


if __name__ == "__main__":
    main()

Частые ошибки

1. Забыть пересечь отрезок друга с [X, Y]

Если использовать сразу [A_i, B_i], можно учитывать дни, которые вообще нельзя выбрать.

Правильно так:

• l = max(A_i, X)
• r = min(B_i, Y)

2. Неправильно обработать включённость правой границы

Если друг занят на [l, r], то убирать его вклад нужно именно в r + 1, а не в r.

3. Забыть про хвост после последнего события

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

4. Пытаться перебирать все дни

При Y - X порядка 10^9 это не сработает по времени.

Небольшой пример вручную

Пусть:

• N = 4
• X = 5, Y = 10

• занятость друзей:

  • [1, 3]
  • [6, 8]
  • [5, 5]
  • [9, 12]

Пересечём с [5, 10]:

• [1, 3] -> не влияет
• [6, 8] -> [6, 8]
• [5, 5] -> [5, 5]
• [9, 12] -> [9, 10]

События:

• 5 -> +1
• 6 -> +1
• 6 -> -1 от отрезка [5, 5]
• 9 -> -1
• 9 -> +1
• 11 -> -1

После суммирования одинаковых точек:

• 5 -> +1
• 6 -> 0
• 9 -> 0
• 11 -> -1

Теперь:

• на дне 5 занят 1 друг;
• на днях 6..10 тоже занят 1 друг.

Минимум занятых равен 1, значит максимум свободных равен 4 - 1 = 3.

Итого

В этой задаче ключевая идея — не думать о каждом дне отдельно, а смотреть только на моменты, где число занятых меняется.

Это классический приём:

• пересечение с нужным диапазоном;
• события начала и конца;
• префиксная сумма по отсортированным координатам.

Такой подход позволяет решить задачу за O(N log N) даже при очень больших координатах дней.