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

Есть K приёмщиков: нечётные принимают сорт A, чётные — B. Партии рассматриваются по началу, затем окончанию, затем A перед B. Партию берёт свободный приёмщик нужного сорта с минимальным номером; иначе её отправляют на рынок.

После окончания приёмщик отдыхает 5 минут. Выведите число принятых партий и номер приёмщика последней принятой в порядке рассмотрения. K и N ≤ 10 000, время от 0 до 1440, нулевая длительность допустима.

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

Сортируем записи как тройки (start, end, kind). Для каждого сорта заведём две минимальные кучи: номера свободных приёмщиков и пары (время освобождения, номер) занятых.

Перед партией времени start возвращаем в свободную кучу всех приёмщиков её сорта с временем освобождения <= start. Из свободных берём минимальный номер; в занятые кладём (end + 5, номер). Если свободных нет, партия отклонена. Она не ждёт освобождения и не передаётся другому сорту.

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

Каждая принятая партия добавляется в кучу и удаляется не более одного раза. Время O(N log N + N log(K + 1) + K), память O(N + K), включая отсортированный вход.

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

Ввод

3 7
25 26 A
10 20 A
19 19 A
10 12 B
20 90 A
17 22 B
10 15 A

Вывод

6 3
Разбор примера по шагам
Партия после сортировкиРешениеОсвобождение приёмщика
10–12, BНомер 217
10–15, AНомер 120
10–20, AНомер 325
17–22, BНомер 227
19–19, AНа рынокСвободных A нет
20–90, AНомер 195
25–26, AНомер 3; последняя31

В момент 10 сначала рассматривается B до 12, затем A до 15 и A до 20. Их принимают номера 2, 1 и 3. В 19 оба нечётных ещё заняты с учётом паузы. В 20 номер 1 уже доступен; в 25 доступен номер 3. Последняя принятая партия достаётся номеру 3, хотя номер 1 закончит позже.

Код на Python и C++

Начальные списки номеров уже возрастают, поэтому удовлетворяют свойству минимальной кучи. Английские A и B сортируются в нужном порядке.

В C++ кучи — priority_queue. По умолчанию она отдаёт наибольший элемент, поэтому третьим параметром указан greater: так сверху оказывается наименьший, как в heapq.

import heapq
import sys


def solve(k, records):
    free = [list(range(1, k + 1, 2)), list(range(2, k + 1, 2))]
    busy = [[], []]
    accepted = last = 0
    for start, end, kind in sorted(records):
        group = 0 if kind == 'A' else 1
        while busy[group] and busy[group][0][0] <= start:
            _, receiver = heapq.heappop(busy[group])
            heapq.heappush(free[group], receiver)
        if not free[group]:
            continue
        receiver = heapq.heappop(free[group])
        heapq.heappush(busy[group], (end + 5, receiver))
        accepted += 1
        last = receiver
    return accepted, last


if __name__ == '__main__':
    stream = sys.stdin
    k, n = map(int, stream.readline().split())
    records = []
    for _ in range(n):
        start, end, kind = stream.readline().split()
        records.append((int(start), int(end), kind))
    print(*solve(k, records))
#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

int main() {
    int k, n;
    cin >> k >> n;
    vector<tuple<long long, long long, char>> records(n);
    for (auto& [start, end, kind] : records)
        cin >> start >> end >> kind;
    sort(records.begin(), records.end());
    // Минимальные кучи: номера свободных и пары (время освобождения, номер) занятых.
    priority_queue<int, vector<int>, greater<int>> free[2];
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> busy[2];
    for (int receiver = 1; receiver <= k; receiver++)
        free[receiver % 2 == 1 ? 0 : 1].push(receiver);
    int accepted = 0, last = 0;
    for (auto [start, end, kind] : records) {
        int group = kind == 'A' ? 0 : 1;
        while (!busy[group].empty() && busy[group].top().first <= start) {
            free[group].push(busy[group].top().second);
            busy[group].pop();
        }
        if (free[group].empty())
            continue;
        int receiver = free[group].top();
        free[group].pop();
        busy[group].push({end + 5, receiver});
        accepted += 1;
        last = receiver;
    }
    cout << accepted << ' ' << last << endl;
}

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

  • Дать приёмщику ждать партию или партии ждать

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

  • Не прибавить пять минут

    Приёмщик доступен только начиная с end + 5. В точности в этот момент новую партию принять уже можно.

  • Выбрать последнего по окончанию

    Последняя принятая партия определяется порядком сортировки и успешного назначения, а не временем завершения.