题目回顾

机场共有 $n$ 个廊桥，划分成国内区和国际区两部分，国内航班只能停靠国内区廊桥，国际航班只能停靠国际区廊桥。廊桥使用严格遵循‌先到先得‌规则：所有航班抵达时，如果对应区域还有空闲廊桥，就直接停靠编号最小的空闲廊桥，否则停靠远机位，机场仅有的一条跑道保证不会出现两架飞机同时抵达的情况。

现在给定所有国内、国际航班的抵达和离开时刻，你需要把全部 $n$ 个廊桥分配给国内区和国际区，找到能让停靠在廊桥的飞机总数量最大的分配方案，输出这个最大总数量。

内容分析

让我们先假设廊桥数量无限来安排航班。我们维护一个空闲的廊桥队列，每到达一架航班，就给它安排编号最小的廊桥供其使用。

现在加上廊桥数量的限制。容易发现刚才的廊桥分配方法直接就帮我们解决了廊桥限制的问题：如果当前有 $n$ 个廊桥可供使用，则分配到 $n+1$ 号及以后的廊桥实质上就是分配到远机位了，不需要再做任何额外的处理。

因此，我们只需对国内和国际航班分别进行模拟，记录每个编号廊桥的服务航班数并求前缀和。最后枚举分配给国内区的廊桥数量,答案即为 $s1[i] + s2[n-i]$ 的最大值。

代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int const N = 1e5 + 10;
struct Node {
	ll l, r;
} a[N], b[N];//飞机进入与离开时间
ll n, m1, m2, ans;
ll s1[N], s2[N];//s[i]表示有i个廊桥有多少飞机能用到

bool cmp(Node x, Node y) {
	if (x.l != y.l) {
		return x.l < y.l;
	}
	return x.r < y.r;
}

ll f(ll m, Node t[], ll s[]) {
	sort(t + 1, t + 1 + m, cmp);
	
	//用两个小根堆记录重要信息 
	priority_queue<ll, vector<ll>, greater<ll>> ip;
	//空闲的廊桥编号
	priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> wait;
	//等待离开的飞机离开时间与所占用的廊桥编号
	
	for (int i = 1; i <= n; i++) {
		ip.push(i);
	}//一开始所有廊桥全部空闲
	
	for (int i = 1; i <= m; i++) {
		while (!wait.empty() && wait.top().first < t[i].l) {
			ip.push(wait.top().second);
			wait.pop();
			//释放对应廊桥
		}//在第i架飞机进入时是否有飞机离开
		if (ip.empty()) {
			continue;
		}//如果没有空闲廊桥就不管否则飞机占用一个廊桥
		ll st = ip.top();
		s[st]++;
		ip.pop();
		//第st个廊桥被使用			
		wait.push({t[i].r, st});
		//第i架飞机进入并占用廊桥
	}
	
	for (int i = 2; i <= m; i++) {
		s[i] += s[i - 1];
	}//计算累加和
}
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);//同步流
		
	cin >> n >> m1 >> m2;
	for (int i = 1; i <= m1; i++) {
		cin >> a[i].l >> a[i].r;
	}
	for (int i = 1; i <= m2; i++) {
		cin >> b[i].l >> b[i].r;
	}
	//输入
	
	f(m1, a, s1);
	f(m2, b, s2);
	
	for (int i = 0; i <= n; i++) {
		ans = max(ans, s1[i] + s2[n - i]);
	}//寻找最多能有多少飞机能用廊桥
	cout << ans;
	return 0;
}