区间分组

例题

区间分组-acwing

区间分组-acwing

分析

对于区间问题, 我们还是首先将其按照某一侧端点排序, 这里我们选择左端点.

我们记录每个已选择区间分组的最大右端点 maxR 的值, 从左到右遍历排序后的区间 range.

1. 如果 range.l 不大于所有分组中最小的 maxR(说明分组的 maxR 可以用小根堆存储), 那么说明这个区间和之前所有的分组一定有交集, 只能新建一个分组.
2. 反之, range.l 大于所有分组中最小的 maxR, 说明它可以分到对应的组中, 只需要更新对应的组的 maxR 即可.

public class acwing_906 {

    record Entry(int l, int r) implements Comparable<Entry> {
        @Override
        public int compareTo(Entry o) {
            return Integer.compare(l, o.l);
        }
    }

    static Entry[] a;

    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(reader.readLine());

        a = new Entry[n];

        for (int i = 0; i < n; i++) {
            String[] nums = reader.readLine().split(" ");

            int l = Integer.parseInt(nums[0]);
            int r = Integer.parseInt(nums[1]);

            a[i] = new Entry(l, r);
        }

        Arrays.sort(a);

        Queue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            Entry e = a[i];
            if (heap.isEmpty() || heap.peek() >= e.l) heap.add(e.r);
            else {
                heap.poll();
                heap.add(e.r);
            }
        }

        System.out.println(heap.size());
    }
}

思考:

为什么以上的代码不能改为右端点排序(其他逻辑不变)?