链接：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≤10e9,1≤N≤10e9,1≤M≤10e5
优先队列以左第一优先，长度第二优先。
不断更新当前边界值
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
PriorityQueue<Code> pq = new PriorityQueue<Code>();
int n = sc.nextInt();
int m = sc.nextInt();
for(int i = 0;i<m;i++) {
pq.add(new Code(sc.nextInt(), sc.nextInt()));
}
int L = 0;
Code pre = new Code(0, 0);
int cont = 1;
while(!pq.isEmpty()) {
Code c=pq.poll();
if(c.left<=L+1) {
if(c.right>pre.right) {
pre = c;
}
}else {
if(c.left>1+pre.right) {
System.out.println(-1);
return;
}
if(pre.right>=n) {
System.out.println(cont);
return;
}
cont++;
L = pre.right;
pre = c;
}
}
if(pre.right>=n) {
System.out.println(cont);
}else{
System.out.println(-1);
}
}
}
class Code implements Comparable<Code> {
int left;
int right;
int len;
public Code(int left, int right) {
this.left = left;
this.right = right;
this.len = right-left;
}
@Override
public String toString() {
return "Code [left=" + left + ", right=" + right + ", len=" + len + "]";
}
@Override
public int compareTo(Code c) {
return left - c.left==0?len-c.len:left-c.left ;
}
}
