思路与算法

每区用全n个桥，按到达顺序把飞机分给最小可用桥号，用忙碌结束堆与空闲桥号堆维护；桥号服务次数的前缀就是该区任意桥数的先到先得服务量。枚举国内分配i。

正确性说明

最小桥号规则中，飞机被分给大于i的桥时，前i个桥当时必全忙；这些高号桥的后续释放不影响前i桥。因此在所有n桥运行中只观察前i桥，与独立只有i桥的先到先得过程完全一致。两区互不干扰，枚举所有i合并前缀即全局最优。

复杂度

O((m1+m2+n)log n)时间、O(m1+m2+n)空间，含两个区的桥堆初始化、排序与服务前缀。

易错点

不能把问题当作可拒绝早到长航班的区间调度；所有事件时刻互不相同，释放时刻严格早于下一到达。允许某区分到0桥。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
vector<int> calc(vector<pair<int, int>> a, int n) {
    sort(a.begin(), a.end());
    priority_queue<int, vector<int>, greater<int>> free;
    for (int i = 1; i <= n; i++)
        free.push(i);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> busy;
    vector<int> cnt(n + 1);
    for (auto p : a) {
        while (!busy.empty() && busy.top().first < p.first) {
            free.push(busy.top().second);
            busy.pop();
        }
        if (free.empty())
            continue;
        int i = free.top();
        free.pop();
        cnt[i]++;
        busy.push({p.second, i});
    }
    for (int i = 1; i <= n; i++)
        cnt[i] += cnt[i - 1];
    return cnt;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m1, m2;
    cin >> n >> m1 >> m2;
    vector<pair<int, int>> a(m1), b(m2);
    for (auto &p : a)
        cin >> p.first >> p.second;
    for (auto &p : b)
        cin >> p.first >> p.second;
    auto x = calc(a, n), y = calc(b, n);
    int ans = 0;
    for (int i = 0; i <= n; i++)
        ans = max(ans, x[i] + y[n - i]);
    cout << ans << "\n";
}