Leetcode 2406. Divide Intervals Into Minimum Number of Groups

[Woodyiiiiiii]

这题显然用到O(nlgn)甚至O(n)级别的时间复杂度。

难点在于：

1. 如何判断两个区间是否重合
2. 如何对区间进行分组
3. 选择哪个区间进行合并

逻辑：
既然用到这么短的时间复杂度了，那么尝试下贪心+排序+堆来解决。

先对数组排序，对区间起点按顺序排序，再对区间终点按顺序排序。这样一来，如果对数组从0-n遍历，判断两个数组是否overlap则通过start <= end // start表示后一个区间的起点，end表示前一个区间的终点即可。

那么如何选择合适的区间呢，使其尽量使得最终结果最小，则尽量让区间更紧凑，则考虑到用最小堆来存储每个区间集合的最大end值。同时堆也有个贪心的作用，如果最小的end都大于等于start，说明这个区间跟其他区间集合都overlap，则加入堆中；否则加入最小的end的区间集合。

class Solution {
    public int minGroups(int[][] intervals) {
        Arrays.sort(intervals, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int[] interval : intervals) {
            if (pq.isEmpty()) {
                pq.offer(interval[1]);
            } else {
                if (pq.peek() >= interval[0]) {
                    pq.offer(interval[1]);
                } else {
                    pq.poll();
                    pq.offer(interval[1]);
                }
            }
        }
        
        return pq.size();
    }
}

---

• 题目地址
• 中文解法
• 英文解法
• interval题目1