题解：洛谷 P1803 凌乱的yyy / 线段覆盖

题目https://www.luogu.com.cn/problem/P1803

题目大意

给定  条线段，第  条线段放在位置 ，现在你需要从这些线段中拿出一些，使得剩下的线段不会重叠。

思路

考虑贪心。

可以发现，按照左端点从小到大排序毫无意义（虽然样例能过）。

因此考虑按右端点从小到大排序。

然后尽量多放线段，如果 （ 代表上次放置的线段的下标），则我们放上  号线段，同时累加答案和更新 。

实现

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,ans;
struct node{
	int x,y;
	bool operator<(const node &T)const{
		return y<T.y;
	}
}a[1000005];
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+n+1);
	for(int i=1,r=0;i<=n;i++){
		if(r<a[i].x+1){
			ans++;
			r=a[i].y;
		}
	}
	cout<<ans;
	return 0;
}