本文共 1558 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要将给定的闭区间分成若干组，使得每组内部的区间两两之间没有交集，并且组数尽可能小。我们可以使用贪心算法和优先队列（堆）来高效地解决这个问题。

方法思路

这种方法确保了每次处理一个区间时，我们总是选择当前能够容纳它的最小的组，从而尽可能减少组数。

解决代码

import java.io.BufferedReader;
import java.util.PriorityQueue;
class Main {
    static int n = 0;
    static PriorityQueue
   
     heap = new PriorityQueue<>();
    public static void main(String[] args) throws Exception {
        BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.valueOf(buf.readLine());
        int[][] nums = new int[n][2];
        int t = 0;
        while (n-- != 0) {
            String[] info = buf.readLine().split(" ");
            int a = Integer.valueOf(info[0]);
            int b = Integer.valueOf(info[1]);
            nums[t][0] = a;
            nums[t][1] = b;
            t++;
        }
        Arrays.sort(nums, (a, b) -> a[0] - b[0]);
        for (int i = 0; i < t; ++i) {
            if (!heap.isEmpty() && heap.peek() >= nums[i][0]) {
                heap.poll();
                heap.add(nums[i][1]);
            } else {
                heap.add(nums[i][1]);
            }
        }
        System.out.print(heap.size());
    }
}
   

代码解释

这种方法的时间复杂度主要由排序和堆操作决定，均为 O(N log N)，适用于较大的数据量。

转载地址：http://tyre.baihongyu.com/