合并区间

题意

给定区间集合，合并所有重叠区间。

思路

暴力反复合并 O(n²) 效率低。排序后只需一次扫描：按左端点排序，维护当前合并区间。新区间与当前区间相交则扩展右端点，否则输出当前区间并开启新区间。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/**
 * Author by Rainboy
 */
// main.cpp：按左端点排序，遍历合并 O(n log n)。
#include <bits/stdc++.h>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(2));
    for (int i = 0; i < n; i++)
        cin >> a[i][0] >> a[i][1];
    auto ans = Solution().merge(a);
    for (auto &v : ans)
        cout << v[0] << ' ' << v[1] << '\n';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#!/usr/bin/env python3
from typing import List


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        ans = []
        for l, r in intervals:
            if not ans or l > ans[-1][1]:
                ans.append([l, r])
            else:
                ans[-1][1] = max(ans[-1][1], r)
        return ans


def main() -> None:
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    ans = Solution().merge(a)
    for l, r in ans:
        print(l, r)


if __name__ == "__main__":
    main()

复杂度

时间复杂度：O(n log n)，排序占主导。
空间复杂度：O(log n) 或 O(n)，取决于排序实现。

总结

区间合并类的核心预处理是排序。排序后只需要看相邻区间是否相交，不需要反复回溯。该模型也适用于区间交、区间差等变体。

目录

题意

思路

代码

复杂度

总结