【洛谷】P2082 区间覆盖（加强版）（经典模拟）

思路：

我们对每个时间从小到大进行排序，每次记录当前连续时间段的起止时间以及截止时间，每次判断下一个时间段的起止时间是否在当前时间内，如果在，即将该时间段归并到当前时间段内，并且更新当前时间段的尾指针，反之对当前时间段马上进行记录，并且马上更新当前时间段的首尾指针。

ACcode:

 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
struct E {
	int s,t;
} e[N];
int n;
bool cmp(E i,E j) {
	return i.s<j.s;
}
void solve() {
	cin>>n;
	for(int i=1; i<=n; i++) cin>>e[i].s>>e[i].t;
	sort(e+1,e+1+n,cmp);
	int ans=0,be=e[1].s,la=e[1].t;
	for(int i=2; i<=n; i++) {
		if(e[i].s>la) {
			ans+=la-be+1;
			be=e[i].s,la=e[i].t;
		} else {
			la=max(la,e[i].t);
		}
	}
	ans+=la-be+1;
	cout<<ans<<"\n";
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t=1;
//	cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}
 
 
 
 

over~