牛客网小白月赛12（华华听月月唱歌）

链接：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 ; 
	}

}