题目地址: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
输入
4 2
1 2
3 4
输出
2
示例2
输入
4 2
1 1
3 4
输出
-1
示例3
输入
10 5
1 1
2 5
3 6
4 9
8 10
输出
4
备注:
1≤L≤R≤109,1≤N≤109,1≤M≤105
解题思路:
贪心,将所有区间按照左端点排序,从左往右遍历。
用一个变量维护我们当前最远可以够到的右端点,然后枚举左端点不超过右端点+1(1 2,3 4这种也是ok的)的所有区间,选择右端点最靠右的,即可更新的最远距离。如果可更新的最远距离没有比之前达到的pre_maxr大,说明存在断点或者已经达到了最远距离,无法再更新,那么就结束遍历。
时间复杂度O(NlogN)。
ac代码:
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef long long ll;
struct node{
int x,y;
friend bool operator <(node a,node b)
{
return a.x==b.x?a.y<b.y:a.x<b.x;
}
}a[maxn];
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++)
scanf("%d %d",&a[i].x,&a[i].y);
sort(a,a+m);
int ans=0,maxr=0;
for(int i=0;i<m;)
{
int r=maxr;
while(a[i].x<=r+1&&i<m)
{
maxr=max(maxr,a[i].y);
i++;
}
if(maxr>r)
ans++;
else
break;
if(maxr>=n) break;
}
if(maxr<n) printf("-1");
else printf("%d",ans);
return 0;
}