P2684 搞清洁

给定一段区间及若干个线段， 求使区间被完全覆盖所需的最少线段数

---

错误日志： 菜

---

Solution

补一下贪心吧

这题最小线段覆盖

首先按照左端点排序

现在对于所有左区间到达目前已覆盖位置， 按照贪心我们选取右区间最右的那个

然后更新即可

注意： 最后还要做一个判断

现在再用最后一个区间， 还不能够到区间右端点， 则无解

若当前已覆盖位置已经大于区间最右， 那么现选取的区间已经完全覆盖了区间

若当前已覆盖位置还未到达区间最右， 前面已经判断过有解， 所以要用上最后一个区间， 答案加一

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#define LL long long

#define REP(i, x, y) for(int i = (x);i <= (y);i++)

using namespace std;

int RD(){

    int out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const int maxn = 50019;

int num, T;

struct Node{int l, r;}I[maxn];

bool cmp(Node a, Node b){return a.l < b.l;}

int main(){

    num = RD(), T = RD();

    REP(i, 1, num){

        I[i].l = RD() - 1;//转换为相交

        I[i].r = RD();

        }

    sort(I + 1, I + 1 + num, cmp);

    int ans = 0, now = 0, next = 0;//next记录当前末尾最长延续

    REP(i, 1, num){

        if(I[i].l <= now)next = max(next, I[i].r);//续上

        else{

            ans++;

            now = next;

            if(I[i].l > now){puts("-1");return 0;}

            next = max(next, I[i].r);//注意新选的区间也要更新最右值

            }

        }

    if(next < T){puts("-1");return 0;}//后面的 next >= T

    if(now < T)printf("%d\n", ans + 1);//选上最后一个区间

    else printf("%d\n", ans);//已经满足要求

    return 0;

    }