Medium

题目描述

给出一个区间的集合，请合并所有重叠的区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：

输入：intervals = [[4,7],[1,4]]
输出：[[1,7]]
解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

提示：

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 10^4

解题思路

这道题的核心思想是排序 + 贪心合并。

基本思路：

  1. 首先按区间的起始位置进行排序，这样可以确保我们按顺序处理区间
  2. 遍历排序后的区间，对于每个区间：
    • 如果当前区间与结果中的最后一个区间不重叠，直接添加到结果中
    • 如果重叠，则合并两个区间（更新结果中最后一个区间的结束位置）

判断重叠的条件： 当前区间的开始时间 <= 上一个区间的结束时间

合并方法： 保持较小的开始时间，取较大的结束时间

时间复杂度分析： 主要消耗在排序上，为 O(n log n)，遍历一次为 O(n)

这种方法简洁高效，是处理区间合并问题的经典解法。通过排序预处理，我们可以保证每次只需要与前一个区间比较，大大简化了逻辑。

代码实现

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.empty()) return {};
        
        sort(intervals.begin(), intervals.end());
        
        vector<vector<int>> result;
        result.push_back(intervals[0]);
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] <= result.back()[1]) {
                result.back()[1] = max(result.back()[1], intervals[i][1]);
            } else {
                result.push_back(intervals[i]);
            }
        }
        
        return result;
    }
};

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        
        intervals.sort(key=lambda x: x[0])
        
        result = [intervals[0]]
        
        for i in range(1, len(intervals)):
            if intervals[i][0] <= result[-1][1]:
                result[-1][1] = max(result[-1][1], intervals[i][1])
            else:
                result.append(intervals[i])
        
        return result

public class Solution {
    public int[][] Merge(int[][] intervals) {
        if (intervals.Length == 0) return new int[0][];
        
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
        
        var result = new List<int[]>();
        result.Add(intervals[0]);
        
        for (int i = 1; i < intervals.Length; i++) {
            if (intervals[i][0] <= result[result.Count - 1][1]) {
                result[result.Count - 1][1] = Math.Max(result[result.Count - 1][1], intervals[i][1]);
            } else {
                result.Add(intervals[i]);
            }
        }
        
        return result.ToArray();
    }
}

var merge = function(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);

    const result = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const current = intervals[i];
        const last = result[result.length - 1];

        if (current[0] <= last[1]) {
            last[1] = Math.max(last[1], current[1]);
        } else {
            result.push(current);
        }
    }

    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要消耗在排序，其中 n 是区间数量
空间复杂度O(log n)排序所需的栈空间，不计算输出数组

相关题目