[Acwing] 算法基础课总结 六 贪心

区间问题 1.区间选点

题意 : 给定多个区间,找到最少的点,使得每个区间至少包含一个点 思路 : 我们把相交区间分为上面大致三种

我们固定一个答案 R R R,表示当前贪心的右端点

显然如果按照左端点进行排序之后,绿色那种情况其实在枚举的时候,会转变为蓝色的那种情况

因此当两个区间不相交的时候 R = a [ i ] . r , + + r e s R=a[i].r,++res R=a[i].r,++res 否则当两个区间相交的时候,我们取较小的 R R R,因为这样子可以包含更多的区间

typedef priority_queue  Pri_m;
typedef pair pii;
typedef vector VI;
map mp;
const int N = 2e5+10,INF = 0x3f3f3f3f;
const double eps = 1e-5;
void solve(){
	vector v;
	int n;cin>>n;
	for(int i=1;i>l>>r;
		v.pb({l,r});
	}
	sort(all(v));
	int res = 0;
	int R = -INF;
	for(auto u : v){
		if(u.x r;
		v.pb({l,r});
	}
	sort(all(v));
	int res = 0;
	int R = -INF;
	for(auto u : v){
		if(u.x a>>b;
		v.pb({a,b});
	}
	sort(all(v));
	
	int res = 0;
	
	for(int i = 0 ; i