来自 @dqstz，仅供讨论，违规删除。

首先有个结论：前 $i$ 个廊桥时可以停靠的飞机在有 $i+1$ 个廊桥时一定可以停靠。

然后考虑求出 $i$ 个廊桥时比 $i-1$ 个廊桥多出来的飞机数，考虑停靠飞机 $j$ 则到达时间在 $[l_j,r_j]$ 中的飞机不能停靠，找到 $l_k>r_j$ 的最小的没有选过的 $k$ 则是下一个可以停靠的飞机，考虑使用并查集，选择第 $j$ 个飞机时将集合 $j$ 合并至 $j+1$，则 $l_k>r_j$ 的最小的 $k$ 所在的集合编号最大的点就是所求的。

这样我们得到了一个 $\Theta(n\log n)$ 的算法：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	
}
const int N=1e5+10;
int f[N],n,m1,m2,ans1[N],ans2[N];
struct node{
	int l,r;
	inline friend operator<(const node &a,const node &b){
		return a.l<b.l;
	}
}a[N],b[N];
inline int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
int main(){
	n=read(),m1=read(),m2=read();
	if(n>=m1+m2)
		return printf("%d",m1+m2),0;
	for(int i=1;i<=m1;i++)
		a[i].l=read(),a[i].r=read();
	for(int i=1;i<=m2;i++)
		b[i].l=read(),b[i].r=read();
	sort(a+1,a+m1+1);
	sort(b+1,b+m2+1);
	for(int i=1;i<=m1+1;i++)
		f[i]=i;
	for(int i=1;i<=m1;i++){
		int ans=0;
		for(int j=0;j<=m1;){
			j=find(lower_bound(a+1,a+m1+1,(node){a[j].r+1,0})-a);
			if(j>m1) break;
			f[j]=j+1;
			ans++;
		}
		ans1[i]=ans1[i-1]+ans;
	}
	for(int i=1;i<=m2+1;i++)
		f[i]=i;
	for(int i=1;i<=m2;i++){
		int ans=0;
		for(int j=0;j<=m2;){
			j=find(lower_bound(b+1,b+m2+1,(node){b[j].r+1,0})-b);
			if(j>m2) break;
			f[j]=j+1;
			ans++;
		}
		ans2[i]=ans2[i-1]+ans;
	}
	int ans=0;
	for(int i=0;i<=n;i++)
		ans=max(ans,ans1[i]+ans2[n-i]);
	write(ans);
	flush();
}

有三个瓶颈：

• sort，可以使用基数排序代替。
• lower_bound，可以双指针预处理。
• 并查集，考虑维护 $f$ 的同时维护集合中的最大值，即可启发式合并/按秩合并，至此总时间复杂度可以做到 $\Theta(n \alpha(n))$。如果使用线性树上并查集，则可优化至 $\Theta(n)$（？）。

感谢！