如何证明cnt == Ans
因为Ans是所有方案的最小值,所以Ans <= cnt自然成立
我们选取一种情况,整个cnt个区间都有公共点,开创第cnt个组时,说明L(i)被包括在前cnt - 1个组当中。
所以cnt个区间必须单独在一个组中,所以Ans >= cnt
所以Ans == cnt
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
public class Main {
static final int N = 100100;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
Range[] ranges = new Range[N];
for (int i = 0; i < n; i++ ) {
String[] s2 = br.readLine().split(" ");
int l = Integer.parseInt(s2[0]);
int r = Integer.parseInt(s2[1]);
ranges[i] = new Range(l, r);
}
Arrays.sort(ranges, 0, n);//按左端点排序
PriorityQueue<Integer> heap = new PriorityQueue<>();//存放所有组中最小的Max_r
//Max_r是一个组中最大的右端点,如果L[i] > Max_r,没有重叠,加入到这个组中,否则新开一个组
//当L[i] > 大于所有组的Max_r时,我们可以任取一个组加入,使用小根堆的话,加入的是Max_r最小的组
for (int i = 0; i < n; i ++ ) {
Range range = ranges[i];
//加入到一个组中
if (heap.isEmpty() || range.l <= heap.peek())
heap.add(range.r);
else {//建一个新组
heap.poll();
heap.add(range.r);
}
}
System.out.println(heap.size());
}
}
class Range implements Comparable<Range> {
int l, r;
public Range (int l, int r) {
this.l = l;
this.r = r;
}
@Override
public int compareTo(Range o) {
return Integer.compare(this.l, o.l);
}
}