⭐ 题目日期：

华为 - 2024/12/3，字节 - 2024/9/29

🌳 题目描述：

一个大列表里面包括若干个包括两个整数的小列表，如 [[1, 2], [3, 6], [4, 7]]，每个小列表代表一个范围 [start, end] ，合并其中重叠的范围并输出。

示例 1：
输入：intervals = [[1, 2], [3, 6], [4, 7]]
输出：[[1, 2], [3, 7]]

解释图例：

🕵🏽‍♂️ 面试评估：

这道题主要是考察候选者是否能首先认识到要进行排序操作来方便后续的合并，是否能够正确应用排序算法来对区间进行排序，并使用双指针策略来合并区间。

🧗难度系数：

⭐️ ⭐️ ⭐️

📝思路分析：

这道题如果正常乱序合并的时间复杂度为 O(n²)，不高效的点在于当前的区间需要跟遍历过的所有区间去比对。为了避免重复比对，我们将区间在 X 轴上标注，再用直线 X = 0 向右移动，如果直线同时穿过两个区间，说明两个区间相交，则将其合并成一个区间。继续移动直线，直到所有元素的区间都被覆盖到。

将以上的逻辑转化成算法，我们需要对区间按照起始值升序排序，排序后的区间顺序也就是直线移动会穿过区间的先后顺序。 然后，进行遍历与合并：

• 将当前区间与结果集中最后一个区间合并。
• 如果当前区间的起点大于上一个区间的终点，说明它们不重叠，可以直接加入结果集。
• 如果当前区间的起点小于等于上一个区间的终点，说明它们重叠，可以合并。更新结果集中最后一个区间的终点为两者的最大值。

用一个具体案例来进行详细分析： 通过排序后，区间变为：[[1, 2], [3, 6], [4, 7]]

~~图解如下：

💻代码(Java、Python、C++)：

Java

public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) {
        return new int[0][2];
    }

    // 对输入的区间开始排序，按照每个区间的起始值升序排序
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

    List<int[]> result = new ArrayList<int[]>();

    for (int[] interval : intervals) {
        // 如果结果集为空，或者是当前区间与结果集中最后一个区间不重叠，就加入结果集中
        if (result.isEmpty() || result.get(result.size() - 1)[1] < interval[0]) {
            result.add(interval);
        } else {
            // 合并区间：更新终点为两者的较大值
            result.get(result.size() - 1)[1] = Math.max(result.get(result.size() - 1)[1], interval[1]);
        }
    }

    return result.toArray(new int[result.size()][]);
}

Python

def merge(self, intervals):
    if not intervals:
        return []

    # 对区间按照起点升序排序
    intervals.sort(key=lambda x: x[0])

    result = []

    for interval in intervals:
        # 如果结果集为空，或者当前区间与结果集中最后一个区间不重叠
        if not result or result[-1][1] < interval[0]:
            result.append(interval)
        else:
            # 合并区间：更新终点为两者的较大值
            result[-1][1] = max(result[-1][1], interval[1])

    return result

C++

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) {
        return {};
    }

    // 按照区间的起始值升序排序
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });

    vector<vector<int>> result;

    for (const auto& interval : intervals) {
        // 如果结果集为空，或者当前区间与结果集最后一个区间不重叠，就直接加入结果集
        if (result.empty() || result.back()[1] < interval[0]) {
            result.push_back(interval);
        } else {
            // 合并区间：更新终点为两者的较大值
            result.back()[1] = max(result.back()[1], interval[1]);
        }
    }

    return result;
}

🚵🏻复杂度分析：

• 时间复杂度：O(n log n)，其中 n 是区间的个数。对区间按起始值进行升序排序的时间复杂度为 O(n log n)；合并的时间复杂度为 O(n)，因为每个区间最多处理一次，所以总的时间复杂度为 O(n log n)。
• 空间复杂度：O(n)，用于存储结果。

🔬在线评测(Online Judge):

题目链接