合并区间问题

题解思路

本题的核心在于区间合并，首先要对区间进行排序，然后通过遍历并合并相邻区间的方式来消除重叠的部分。

具体步骤如下：

1. 排序：首先按照区间的起点 start 进行升序排序，如果 start 相同，则按照 end 排序（默认即可）。
2. 合并区间：
   • 使用一个 merged 列表存储合并后的区间。
   • 遍历排序后的区间：
     • 如果 merged 为空，或者当前区间的 start 大于 merged 最后一个区间的 end，说明它们不重叠，直接加入 merged。
     • 否则，说明有重叠，合并方式是：更新 merged 最后一个区间的 end 为 max(当前区间的end, merged最后一个区间的end)。

复杂度分析

• 排序：时间复杂度为 O(n log n)。
• 遍历合并：一次遍历，时间复杂度为 O(n)。
• 总复杂度：主要由排序决定，即 O(n log n)。

代码实现

Python 实现

class Solution:
    def merge(self, intervals):
        if not intervals:
            return []
        
        # 1. 先按照区间的起点排序
        intervals.sort()
        
        merged = []
        for interval in intervals:
            # 2. 如果结果数组为空，或者当前区间与前一个区间不重叠，直接加入
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # 3. 否则有重叠，更新 merged 最后一个区间的右边界
                merged[-1][1] = max(merged[-1][1], interval[1])
        
        return merged

if __name__ == "__main__":
    n = int(input())  # 读取区间数量
    intervals = [list(map(int, input().split())) for _ in range(n)]  # 读取所有区间

    solution = Solution()
    result = solution.merge(intervals)

    for start, end in result:
        print(start, end)

Java 实现

import java.util.*;

public class Main {
    public class Solution {
        public List<int[]> merge(int[][] intervals) {
            List<int[]> merged = new ArrayList<>();
            if (intervals.length == 0) return merged;

            // 1. 先按照区间的起点进行排序
            Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

            for (int[] interval : intervals) {
                // 2. 如果结果数组为空，或者当前区间与前一个区间不重叠，直接加入
                if (merged.isEmpty() || merged.get(merged.size() - 1)[1] < interval[0]) {
                    merged.add(interval);
                } else {
                    // 3. 否则有重叠，更新 merged 最后一个区间的右边界
                    merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], interval[1]);
                }
            }
            return merged;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 读取区间数量
        int[][] intervals = new int[n][2];

        for (int i = 0; i < n; i++) {
            intervals[i][0] = scanner.nextInt();
            intervals[i][1] = scanner.nextInt();
        }
        scanner.close();

        Main main = new Main();
        Solution solution = main.new Solution();
        List<int[]> result = solution.merge(intervals);

        for (int[] interval : result) {
            System.out.println(interval[0] + " " + interval[1]);
        }
    }
}

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> merged;
        if (intervals.empty()) return merged;

        // 1. 按照区间的起点排序
        sort(intervals.begin(), intervals.end());

        for (auto& interval : intervals) {
            // 2. 如果 merged 为空或者当前区间与前一个区间不重叠，直接加入
            if (merged.empty() || merged.back()[1] < interval[0]) {
                merged.push_back(interval);
            } else {
                // 3. 否则有重叠，更新 merged 最后一个区间的右边界
                merged.back()[1] = max(merged.back()[1], interval[1]);
            }
        }
        return merged;
    }
};

int main() {
    int n;
    cin >> n;  // 读取区间数量
    vector<vector<int>> intervals(n, vector<int>(2));

    for (int i = 0; i < n; i++) {
        cin >> intervals[i][0] >> intervals[i][1];
    }

    Solution solution;
    vector<vector<int>> result = solution.merge(intervals);

    for (auto& interval : result) {
        cout << interval[0] << " " << interval[1] << endl;
    }
    return 0;
}

Leetcode 14.合并区间-原题链接

题目内容

以数组 $intervals$ 表示若干个区间的集合，其中单个区间为 $intervals[i] = [start_i, end_i]$ 。请你合并所有重叠的区间，并输出一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

输入描述

第一行为一个整数 $n$ ，代表数组 $intervals$的长度。 接下来的$n$行，每行有两个整数$start_i, end_i$，代表第$i$个区间。

输出描述

如题，每行输出一个区间，区间的数字以空额分隔。每个区间以$start_i$升序输出。

样例1

输入

4
1 3
2 6
8 10
15 18

输出

1 6
8 10
15 18

说明

区间 $[1,3] 和 [2,6]$重叠, 将它们合并为$[1,6]$

样例2

输入

2 
1 4
4 5

输出

1 5

说明

区间$[1,4]$和 $[4,5]$ 可被视为重叠区间。

提示

• $1 <= intervals.length <= 10^4$
• $intervals[i].length == 2$
• $0 <= start_i <= end_i <= 10^4$