Question

2406. 将区间分为最少组数

English Version

题目描述

给你一个二维整数数组 intervals ，其中 intervals[i] = [lefti, righti] 表示 闭 区间 [lefti, righti] 。

你需要将 intervals 划分为一个或者多个区间 组 ，每个区间 只 属于一个组，且同一个组中任意两个区间 不相交 。

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

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

 

示例 1：

输入：intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
输出：3
解释：我们可以将区间划分为如下的区间组：
- 第 1 组：[1, 5] ，[6, 8] 。
- 第 2 组：[2, 3] ，[5, 10] 。
- 第 3 组：[1, 10] 。
可以证明无法将区间划分为少于 3 个组。

示例 2：

输入：intervals = [[1,3],[5,6],[8,10],[11,13]]
输出：1
解释：所有区间互不相交，所以我们可以把它们全部放在一个组内。

 

提示：

• 1 <= intervals.length <= 105
• intervals[i].length == 2
• 1 <= lefti <= righti <= 106

解法

方法一：贪心 + 优先队列（小根堆）

我们先将区间按左端点排序，用小根堆维护每组的最右端点（堆顶是所有组的最右端点的最小值）。

接下来，我们遍历每个区间：

• 若当前区间左端点大于堆顶元素，说明当前区间可以加入到堆顶元素所在的组中，我们直接弹出堆顶元素，然后将当前区间的右端点放入堆中；
• 否则，说明当前没有组能容纳当前区间，那么我们就新建一个组，将当前区间的右端点放入堆中。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 intervals 的长度。

class Solution:
  def minGroups(self, intervals: List[List[int]]) -> int:
    h = []
    for a, b in sorted(intervals):
      if h and h[0] < a:
        heappop(h)
      heappush(h, b)
    return len(h)

class Solution {
  public int minGroups(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> q = new PriorityQueue<>();
    for (var e : intervals) {
      if (!q.isEmpty() && q.peek() < e[0]) {
        q.poll();
      }
      q.offer(e[1]);
    }
    return q.size();
  }
}

class Solution {
public:
  int minGroups(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int>> q;
    for (auto& e : intervals) {
      if (q.size() && q.top() < e[0]) {
        q.pop();
      }
      q.push(e[1]);
    }
    return q.size();
  }
};

func minGroups(intervals [][]int) int {
  sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
  q := hp{}
  for _, e := range intervals {
    if q.Len() > 0 && q.IntSlice[0] < e[0] {
      heap.Pop(&q)
    }
    heap.Push(&q, e[1])
  }
  return q.Len()
}

type hp struct{ sort.IntSlice }

func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
  a := h.IntSlice
  v := a[len(a)-1]
  h.IntSlice = a[:len(a)-1]
  return v
}