线段覆盖问题

1.线段不覆盖问题

给出 \(n\) 个线段，选择尽量多的线段使得线段无重叠，问最多可以选多少条线段。

解析

考虑贪心，将线段按右端点从小到大排序，如果这条线段的左端点大于上一条线段的右端点那就选择这条线段。

为什么这么贪是对的呢，因为将右端点排序可以使右边剩余的空间尽量大，那么剩余的选择就可能会更大，而且每个线段对答案贡献都为一，我可以剩下更多的空间，我们价值都为一，那我为什么要给你（贪心真残酷）。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
struct ss{
	int s,t;//s:开始，t:结束
}a[1000005];
bool cmp(ss g,ss h){
	return g.t<h.t;	
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].s>>a[i].t;
	}
	sort(a+1,a+n+1,cmp);
	int last=0,ans=0;//last:上一个选择线段的右端点
	for(int i=1;i<=n;i++){
		if(last<=a[i].s){//因为不能重叠
			ans++;
			last=a[i].t;//更新
		}
	}
	cout<<ans;
    return 0;
}