10pts 9WA 可过样例

思路:

按照左端点作为第一关键字、右端点作为第二关键字排序。每次取出两个区间：

• 如果他们有重叠，合并他们
• 如果没有重叠，答案累加靠前的区间，重新放入后一个区间

提交记录

#include<bits/stdc++.h>
using namespace std;
struct node{
	long long l,r;
	bool operator <(node other)const {
		if(l!=other.l) return l>other.l;
		else return r>other.r;
	}
};
priority_queue<node> q;
long long n,ans;
long long len(node a){
	return a.r-a.l+1;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int l,r;cin>>l>>r;
		q.push({l,r});
	}
	if(n==1){
		cout<<len(q.top());
		return 0;	
	}
	while(q.size()>1){
		node q1=q.top();
		q.pop();
		node q2=q.top();
		q.pop();
		if(q2.l<=q1.r){
			q.push({q1.l,q2.r});
		}else{
			q.push(q2);
			ans+=len(q1);
		}
	}
	cout<<ans+len(q.top());
}