1. Идея

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

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

Главная идея такая:

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

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

2. Наблюдения

Наблюдение 1

Если рейсы отсортированы по времени начала, то для очередного рейса важно только одно: есть ли автобус, который уже свободен к моменту s.

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

Наблюдение 2

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

Наблюдение 3

Если автобус заканчивает рейс в момент e, а следующий рейс начинается в момент s = e, то этот автобус можно использовать снова. Поэтому условие повторного использования — end_time <= s.

Наблюдение 4

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

3. Алгоритм

1. Считываем все рейсы.
2. Для каждого рейса сохраняем:
   • s — начало,
   • e — конец,
   • idx — номер во входных данных.
3. Сортируем рейсы по s, затем по e, затем по idx.
4. Создаем минимальную кучу. В ней будут пары:
   • время освобождения автобуса,
   • номер автобуса.
5. Также создаем массив ans, где ans[idx] — автобус для исходного рейса.
6. Идем по рейсам в отсортированном порядке:
   • если куча не пуста и автобус на вершине освобождается не позже начала текущего рейса, то переиспользуем этот автобус;
   • иначе создаем новый автобус.
7. После назначения автобуса:
   • записываем его номер в ans[idx];
   • добавляем в кучу новую пару (e, bus_id), потому что теперь этот автобус занят до e.
8. В конце выводим:
   • количество использованных автобусов,
   • массив ans.

4. Почему это работает

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

Почему можно обрабатывать рейсы по возрастанию начала

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

Это зависит только от того, освобождается ли хотя бы один автобус к моменту s.

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

Пусть в куче хранится время освобождения каждого занятого автобуса.

• Если самый ранний автобус освобождается позже, чем s, то все остальные освобождаются еще позже. Значит, ни один автобус не подходит.
• Если самый ранний автобус освобождается не позже s, то он подходит, и можно взять его.

То есть вершина кучи полностью отвечает на вопрос: нужен новый автобус или нет.

Почему переиспользование автобуса всегда выгодно

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

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

Почему алгоритм минимален

Новый автобус создается только тогда, когда ни один из текущих автобусов не свободен к моменту s.

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

Итак:

• если алгоритм берет старый автобус, число автобусов не растет;
• если алгоритм создает новый автобус, это действительно необходимо.

Следовательно, итоговое число автобусов минимально.

5. Сложность

Пусть n — число рейсов.

• Сортировка: O(n log n)
• Для каждого рейса один раз делаем извлечение и добавление в кучу: O(log n) на рейс
• Итого: O(n log n)

Память:

• список рейсов,
• массив ответов,
• куча.

Общая дополнительная память: O(n).

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct Trip {
    long long s;
    long long e;
    int idx;
};

int main() {
    int n;
    cin >> n;

    vector<Trip> trips(n);
    for (int i = 0; i < n; i++) {
        cin >> trips[i].s >> trips[i].e;
        trips[i].idx = i;
    }

    sort(trips.begin(), trips.end(), [](const Trip& a, const Trip& b) {
        if (a.s != b.s) return a.s < b.s;
        if (a.e != b.e) return a.e < b.e;
        return a.idx < b.idx;
    });

    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    vector<int> ans(n);
    int buses = 0;

    for (const Trip& t : trips) {
        int bus_id;
        if (!pq.empty() && pq.top().first <= t.s) {
            bus_id = pq.top().second;
            pq.pop();
        } else {
            buses++;
            bus_id = buses;
        }
        ans[t.idx] = bus_id;
        pq.push({t.e, bus_id});
    }

    cout << buses << "\n";
    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << "\n";

    return 0;
}

7. Код на Python 3

import heapq

n = int(input())
trips = []
for i in range(n):
    s, e = map(int, input().split())
    trips.append((s, e, i))

trips.sort()

heap = []
ans = [0] * n
buses = 0

for s, e, idx in trips:
    if heap and heap[0][0] <= s:
        end_time, bus_id = heapq.heappop(heap)
    else:
        buses += 1
        bus_id = buses
    ans[idx] = bus_id
    heapq.heappush(heap, (e, bus_id))

print(buses)
print(*ans)