三类经典贪心问题

区间选点问题

\(n\)个闭区间\([a_i,b_i]\)，选择尽量少的点，使得每个区间至少有一个点

按右端点升序排序，每次选点尽量选择当前区间靠右的点以照顾到更多的区间
所以排序后第一个区间的右端点是一定会选的，然后向后遍历区间直到这个点不在某个区间上
更新点为这个区间的右端点

int ans = 1, k = 0;
for(int i = 0; i < n; i++){
    if(node[i].a > node[k].b)
        ans++, k = i;
}

线段覆盖问题

\(n\)个开区间\((a_i,b_i)\)，选择尽量多个区间，使得这些区间两两不相交

区间选点类似
按右端点升序排序，每次选区间尽量选择右端点靠左的区间以给后面的区间腾出更多的空间
同样，排序后的第一个区间一定会选
因为所有区间的贡献都是1，但是这个区间给后面留的空间更多，所以肯定选这个
向后遍历直到出现不相交区间，更新区间

int ans = 1, k = 0;
for(int i = 0; i < n; i++){
    if(node[i].a >= node[k].b)
	ans++, k = i;
}

区间完全覆盖问题

\(n\)个闭区间\([a_i,b_i]\)，选择尽量少的区间完全覆盖给定的一个区间

按左端点升序排序，维护俩变量\(last\)，\(far\)，分别表示当前已经覆盖到的位置，当前能到达的最远位置

int solve(){
    int cnt = 0;
    double last = 0, far = 0;
    for(int i = 0; i < n;i++){
        if(last >= len) return cnt;
        if(s[i].a <= last) far = max(far, s[i].b);
        else{
            cnt++;
            last = far;
            if(s[i].a <= last) far = max(far, s[i].b);
            else return -1;
        }
    }
    if(last < len && far >= len) return cnt + 1;
    if(far < len ) return -1;
    return cnt;
}