本文共 1529 字，大约阅读时间需要 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/