区间问题
AcWing 905. 区间选点 原题链接
给定N个闭区间[ai,biai,bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
输出选择的点的最小数量。
位于区间端点上的点也算作区间内。
输入格式
第一行包含整数N，表示区间数。
接下来N行，每行包含两个整数ai,biai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需的点的最小数量。
数据范围
1≤N≤1051≤N≤105, −109≤ai≤bi≤109−109≤ai≤bi≤109
输入样例：
3
-1 1
2 4
3 5
输出样例：
2
按左端点排序的做法：
public static void main(String[] args) {
int n = in.nextInt();
int[][] intervals = new int[n][2];
for (int i = 0; i < n; i++) {
intervals[i][0] = in.nextInt();
intervals[i][1] = in.nextInt();
}
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
int r = intervals[0][1];
int res = 1;
for (int i = 1; i < n; i++) {
if (r >= intervals[i][0]) {
r = Math.min(r, intervals[i][1]);
} else {
if (i != 1)
res++;
r = intervals[i][1];
}
}
out.println(res);
out.flush();
out.close();
}
按右端点排序的做法：
public static void main(String[] args) {
int n = in.nextInt();
int[][] intervals = new int[n][2];
for (int i = 0; i < n; i++) {
intervals[i][0] = in.nextInt();
intervals[i][1] = in.nextInt();
}
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
int r = intervals[0][1];
int res = 1;
for (int i = 1; i < n; i++) {
if (r >= intervals[i][0]) {
continue;
} else {
res++;
r = intervals[i][1];
}
}
out.println(res);
out.flush();
out.close();
}
AcWing 908. 最大不相交区间数量 原题链接
给定N个闭区间[ai,biai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。
输入格式
第一行包含整数N，表示区间数。
接下来N行，每行包含两个整数ai,biai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示可选取区间的最大数量。
数据范围
1≤N≤1051≤N≤105, −109≤ai≤bi≤109−109≤ai≤bi≤109
输入样例：
3
-1 1
2 4
3 5
输出样例：
2
public static void main(String[] args) {
int n = in.nextInt();
int[][] intervals = new int[n][2];
for (int i = 0; i < n; i++) {
intervals[i][0] = in.nextInt();
intervals[i][1] = in.nextInt();
}
Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
int r = intervals[0][1];
int res = 1;
for (int i = 1; i < n; i++) {
if (r < intervals[i][0]) {
res++;
r = intervals[i][1];
}else {
r = Math.min(r, intervals[i][1]);
}
}
out.println(res);
out.flush();
out.close();
}
AcWing 906. 区间分组 原题链接
给定N个闭区间[ai,biai,bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
输出最小组数。
输入格式
第一行包含整数N，表示区间数。
接下来N行，每行包含两个整数ai,biai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示最小组数。
数据范围
1≤N≤1051≤N≤105, −109≤ai≤bi≤109−109≤ai≤bi≤109
输入样例：
3
-1 1
2 4
3 5
输出样例：
2
public static void main(String[] args) {
int n = in.nextInt();
int[][] intervals = new int[n][2];
for (int i = 0; i < n; i++) {
intervals[i][0] = in.nextInt();
intervals[i][1] = in.nextInt();
}
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(intervals[0][1]);
for (int i = 1; i < n; i++) {
if (queue.peek() < intervals[i][0]) {
queue.poll();
}
queue.add(intervals[i][1]);
}
out.println(queue.size());
out.flush();
out.close();
}
AcWing 907. 区间覆盖 原题链接
给定N个闭区间[ai,biai,bi]以及一个线段区间[s,ts,t]，请你选择尽量少的区间，将指定线段区间完全覆盖。
输出最少区间数，如果无法完全覆盖则输出-1。
输入格式
第一行包含两个整数s和t，表示给定线段区间的两个端点。
第二行包含整数N，表示给定区间数。
接下来N行，每行包含两个整数ai,biai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示所需最少区间数。
如果无解，则输出-1。
数据范围
1≤N≤1051≤N≤105, −109≤ai≤bi≤109−109≤ai≤bi≤109, −109≤s≤t≤109−109≤s≤t≤109
输入样例：
1 5
3
-1 3
2 4
3 5
输出样例：
2
public static void main(String[] args) {
int[] target = new int[2];
target[0] = in.nextInt();
target[1] = in.nextInt();
int n = in.nextInt();
int[][] intervals = new int[n][2];
for (int i = 0; i < n; i++) {
intervals[i][0] = in.nextInt();
intervals[i][1] = in.nextInt();
}
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
int r = target[0];
int res = 0;
for (int i = 0; i < n; ) {
int idx = -1;
while (i < n && intervals[i][0] <= r) {
if (idx == -1 || intervals[idx][1] < intervals[i][1]) {
idx = i;
}
i++;
}
if (idx == -1) {
break;
}
res++;
r = intervals[idx][1];
if (r >= target[1]) break;
}
if (res == 0 || r < target[1]) {
out.println(-1);
}else {
out.println(res);
}
out.flush();
out.close();
}