acwing算法基础之基础算法--区间合并算法

1 知识点

题目类型：将有交集的区间进行合并。

算法步骤：

1. 先排序区间。
2. 维护一个合并区间，每次把合并区间插入到最终答案中。

2 模板

//对segs进行区间合并操作
void merge(vector<pair<int,int>> &segs) {
    if (segs.size() == 0) { //判断传入的是否为空数组，若是，则不进行后续操作。
        return;
    }
    
    vector<pair<int,int>> res;
    sort(segs.begin(), segs.end());
    
    int l = -2e9, r = -2e9;
    for (auto seg : segs) {
        if (r < seg.first) {
            if (l != -2e9) {
                res.emplace_back(make_pair(l,r));
            }
            l = seg.first;
            r = seg.second;            
        } else {
            r = max(r, seg.second);
        }
    }
    
    res.emplace_back(make_pair(l,r)); //把最后一个区间传入答案中
    
    segs = res;
    
    return;
}
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