[LeetCode] 2406. Divide Intervals Into Minimum Number of Groups

You are given a 2D integer array intervals where intervals[i] = [left, right] represents the inclusive interval [left, right].

You have to divide the intervals into one or more groups such that each interval is in exactly one group, and no two intervals that are in the same group intersect each other.

Return the minimum number of groups you need to make.

Two intervals intersect if there is at least one common number between them. For example, the intervals [1, 5] and [5, 8] intersect.

Example 1:
Input: intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
Output: 3
Explanation: We can divide the intervals into the following groups:

Group 1: [1, 5], [6, 8].
Group 2: [2, 3], [5, 10].
Group 3: [1, 10].
It can be proven that it is not possible to divide the intervals into fewer than 3 groups.

Example 2:
Input: intervals = [[1,3],[5,6],[8,10],[11,13]]
Output: 1
Explanation: None of the intervals overlap, so we can put all of them in one group.

Constraints:
1 <= intervals.length <= 105
intervals[i].length == 2
1 <= left <= right <= 106

将区间分为最少组数。

给你一个二维整数数组 intervals ，其中 intervals[i] = [left, right] 表示闭区间 [left, right] 。
你需要将 intervals 划分为一个或者多个区间组，每个区间只属于一个组，且同一个组中任意两个区间不相交。

请你返回最少需要划分成多少个组。

如果两个区间覆盖的范围有重叠（即至少有一个公共数字），那么我们称这两个区间是相交的。比方说区间 [1, 5] 和 [5, 8] 相交。

思路

此题思路同会议室 II。大致思路都是排序 + 比较，只是具体做法有些区别。以下请把 left 和 right 分别理解为一个会议的开始时间和结束时间。

思路一 - 排序 + 最小堆

初始化的时候对 input 按开始时间排序，然后准备一个最小堆，是用来放入所有会议的结束时间。遍历 input 数组，因为 input 已经按开始时间排过序，所以对于某个开始时间而言，我们拿他去跟堆顶的最小的结束时间比较。如果开始时间跟结束时间有重叠，则说明这两个会议时间是有交集的，一定要再开一个会议室（将当前结束时间放入堆中）。照着此题的题意就是这两个区间一定不能分在同一组。最后最小堆的 size 就是会议室的数量 - 也就是分组的数量。

思路二 - 对 left 和 right 分别排序

对会议的开始时间和结束时间分别排序。用双指针的方式遍历开始时间和结束时间。如果某个结束时间比当前的开始时间小，则说明两个会议没有交集，可以分在同一组。如果某个结束时间比当前的开始时间大，则说明两个会议有交集，就需要再加一组。最后返回组的数量。

复杂度

时间O(nlogn)
空间O(n)

代码

Java实现 - 排序 + 最小堆

class Solution {
    public int minGroups(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> a - b);
        int n = intervals.length;
        for (int i = 0; i < n; i++) {
            int[] cur = intervals[i];
            if (!queue.isEmpty() && queue.peek() < cur[0]) {
                queue.poll();
            }
            queue.offer(cur[1]);
        }
        return queue.size();
    }
}

Java实现 - 对 left 和 right 分别排序

class Solution {
    public int minGroups(int[][] intervals) {
        // corner case
        if (intervals == null || intervals.length == 0) {
            return 0;
        }

        // normal case
        int n = intervals.length;
        int[] start = new int[n];
        int[] end = new int[n];
        for (int i = 0; i < n; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        int res = 0;
        int pointer = 0;
        for (int i = 0; i < n; i++) {
            if (start[i] <= end[pointer]) {
                res++;
            } else {
                pointer++;
            }
        }
        return res;
    }
}

[LeetCode] 2406. Divide Intervals Into Minimum Number of Groups

思路

思路一 - 排序 + 最小堆

思路二 - 对 left 和 right 分别排序

复杂度

代码

相关题目