区间覆盖问题,先排序所有区间,再贪心来做。
import java.util.Arrays;
import java.util.Scanner;
public class E3 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
int n = in.nextInt();
int l = in.nextInt();
int[][] interval = new int[n][2];
for(int i = 0; i < n; ++i) {
interval[i][0] = in.nextInt();
interval[i][1] = in.nextInt();
}
Arrays.sort(interval, (a, b) -> {return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0];});
boolean able = true;
int i = 0, k = 0;
int max = 0; //最右能到的位置
int start = 0; //起始位置
int cnt = 0;//区间数
while(start < l) {
if(interval[k][0] > start) {
able = false;
break;
}
for(i = k; i < n; ++i) {
if(interval[i][0] <= start) {
max = Math.max(interval[i][1], max);
} else {
++cnt;
start = max;
k = i;
break;
}
}
if(i == n) {
++cnt;
break;
}
}
if(able) {
System.out.println(cnt);
} else {
System.out.println(-1);
}
}
}
}