小白贪心题

链接：https://ac.nowcoder.com/acm/contest/392/A
来源：牛客网

题目描述

月月唱歌超级好听的说！华华听说月月在某个网站发布了自己唱的歌曲，于是把完整的歌曲下载到了U盘里。然而华华不小心把U盘摔了一下，里面的文件摔碎了。月月的歌曲可以看成由1到N的正整数依次排列构成的序列，它现在变成了若干个区间，这些区间可能互相重叠。华华想把它修复为完整的歌曲，也就是找到若干个片段，使他们的并集包含1到N（注意，本题中我们只关注整数，见样例1）。但是华华很懒，所以他想选择最少的区间。请你算出华华最少选择多少个区间。因为华华的U盘受损严重，所以有可能做不到，如果做不到请输出-1。

输入描述:

第一行两个正整数N、M，表示歌曲的原长和片段的个数。
接下来M行，每行两个正整数L、R表示第i的片段对应的区间是[L,R]。

输出描述:

如果可以做到，输出最少需要的片段的数量，否则输出-1。

示例1

1.输入

4 2
1 2
3 4

1.输出

2

2.输入

4 2
1 1
3 4

2.输出

-1

3.输入

10 5
1 1
2 5
3 6
4 9
8 10

3.输出

4

备注:

$\mathrm{1\le L\le R\le 109,1\le N\le 109,1\le M\le 105}$





PS:在比赛中思路是正确的，但是代码拍不出来，diss自己，一个简单的贪心。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define Swap(a,b,t) t=a,a=b,b=t
#define Mem0(x) memset(x,0,sizeof(x))
#define Mem1(x) memset(x,-1,sizeof(x))
#define MemX(x) memset(x,0x3f,sizeof(x))
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f;
const double eps=1e-12;
const int MAX=1e5+10;
struct s{
    int left,right;
}map[MAX];
bool cmp(const s &a,const s &b)
{
    if (a.left!=b.left)    return a.left<b.left;
    return a.right>b.right;
}
int main()
{
    int n,k,l,r;
    while (scanf("%d%d",&n,&k)!=EOF){
        for (int i=0;i<k;i++)
            scanf("%d%d",&map[i].left,&map[i].right);
        sort(map,map+k,cmp);
        bool flag=true;
        int l=0,r=0,tmp,ans=0;
        while (l<k&&r<n){
            tmp=0;
            ans++;
            while (l<k&&r<n&&map[l].left<=r+1){
                tmp=max(tmp,map[l].right);
                l++;
            }
            if (tmp==0){
                flag=false;
                break;
            }
            r=tmp;    
        }
        if (flag)
            printf("%d
",ans);
        else
            printf("-1
");
    }
    return 0;
}