LeetCode 56 合并区间(贪心)

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

示例 1:

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

示例 2:

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

思路

一个小贪心，把区间按照左端点排序。初始值设置为第一个区间的左和右。

然后遍历排序好的区间，如果遍历到的区间左端点小于等于r，就扩展r，等到不满足条件时证明这个区间最多就包含这么多，继续下一个区间即可。

代码

 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
class Solution
{
public:
    static bool cmp(pair<int, int> a, pair<int, int> b)
    {
        return a.first < b.first;
    }
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {
        vector<vector<int>> ans;
        if (intervals.size() == 0)
            return ans;
        vector<pair<int, int>> v;
        for (auto interval : intervals)
            v.push_back({interval[0], interval[1]});
        sort(v.begin(), v.end(), cmp);
        auto [l, r] = v[0];
        for (int i = 1; i < v.size(); i++)
        {
            if (v[i].first <= r)
                r = max(r, v[i].second);
            else
            {
                ans.push_back({l, r});
                l = v[i].first;
                r = v[i].second;
            }
        }
        ans.push_back({l, r});
        return ans;
    }
};

最后修改于 2020-04-16

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。