AcWing 803. 区间合并

题目连接

https://www.acwing.com/problem/content/805/

思路

我们先对区间的起点和终点从小到大排序我们很容易发现，区间合并无非三种情况

• 右边区间包含在当前区间内
• 右边区间和当前区间有交集
• 右边区间不在当前区间内

对于第一种情况，当前区间的右端点不会发生变化，对于第二种情况，当前区间的右端点更新，对于第三种情况，当前区间的左右端点都更新，其实这里左端点并没有什么作用

代码

#include
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
int n;
vector V;

int main()
{
	cin>>n;
	for(int i = 1;i >p.first>>p.second;
		V.push_back(p);
	}
	sort(V.begin(),V.end());
	int ans = 0;
	int sx=-1000000000,ed = -1000000000;
	for(int i = 0;i  ed){
			ans++;
			sx = V[i].first;
			ed = V[i].second;
		}
		else {
			if(V[i].second > ed){
				ed = V[i].second;
			}
		}
	}
	cout