Medium

题目描述

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

你需要将区间划分为一个或多个组，使得每个区间恰好属于一个组，且同一组中的任意两个区间不相交。

返回你需要的 最少组数。

如果两个区间之间有至少一个公共数字，那么这两个区间相交。例如，区间 [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 <= 10^5
  • intervals[i].length == 2
  • 1 <= lefti <= righti <= 10^6

解题思路

解题思路

这道题的核心在于理解：最少的组数等于在某个时刻同时重叠的区间的最大数量。

有多种解法可以解决这个问题：

方法一：扫描线算法（推荐）

将问题转化为求在某个时刻同时活跃的区间最大数量。对于每个区间 [left, right]，我们在 left 处 +1（区间开始），在 right+1 处 -1（区间结束后）。然后按位置排序，依次处理这些事件，维护当前活跃区间数的最大值。

方法二：最小堆贪心算法

按区间起始位置排序，用最小堆维护每个组的结束时间。对于新区间，如果它的起始时间大于堆顶（最早结束的组），则可以复用该组；否则需要新建组。

方法三：差分数组

利用差分数组的思想，对每个区间的范围进行标记，最后统计重叠的最大值。但由于坐标范围较大，需要先进行坐标压缩。

扫描线算法时间复杂度最优且实现简洁，是最推荐的解法。

代码实现

class Solution {
public:
    int minGroups(vector<vector<int>>& intervals) {
        vector<pair<int, int>> events;
        
        // 添加区间开始和结束事件
        for (auto& interval : intervals) {
            events.push_back({interval[0], 1});      // 区间开始
            events.push_back({interval[1] + 1, -1}); // 区间结束后
        }
        
        // 按位置排序，结束事件优先处理
        sort(events.begin(), events.end());
        
        int maxGroups = 0, currentGroups = 0;
        for (auto& event : events) {
            currentGroups += event.second;
            maxGroups = max(maxGroups, currentGroups);
        }
        
        return maxGroups;
    }
};

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        events = []
        
        # 添加区间开始和结束事件
        for left, right in intervals:
            events.append((left, 1))      # 区间开始
            events.append((right + 1, -1)) # 区间结束后
        
        # 按位置排序
        events.sort()
        
        max_groups = 0
        current_groups = 0
        for _, delta in events:
            current_groups += delta
            max_groups = max(max_groups, current_groups)
        
        return max_groups

public class Solution {
    public int MinGroups(int[][] intervals) {
        var events = new List<(int pos, int delta)>();
        
        // 添加区间开始和结束事件
        foreach (var interval in intervals) {
            events.Add((interval[0], 1));      // 区间开始
            events.Add((interval[1] + 1, -1)); // 区间结束后
        }
        
        // 按位置排序
        events.Sort();
        
        int maxGroups = 0, currentGroups = 0;
        foreach (var (pos, delta) in events) {
            currentGroups += delta;
            maxGroups = Math.Max(maxGroups, currentGroups);
        }
        
        return maxGroups;
    }
}

var minGroups = function(intervals) {
    const events = [];
    
    // 添加区间开始和结束事件
    for (const [left, right] of intervals) {
        events.push([left, 1]);      // 区间开始
        events.push([right + 1, -1]); // 区间结束后
    }
    
    // 按位置排序
    events.sort((a, b) => a[0] - b[0]);
    
    let maxGroups = 0, currentGroups = 0;
    for (const [pos, delta] of events) {
        currentGroups += delta;
        maxGroups = Math.max(maxGroups, currentGroups);
    }
    
    return maxGroups;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型扫描线算法
时间复杂度O(n log n)
空间复杂度O(n)

其中 n 是区间的数量。时间复杂度主要由排序决定，空间复杂度用于存储事件数组。

相关题目