合并区间

发表于 | 更新于：

题目地址

LeetCode#56 合并区间

题目描述

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

示例：
给出 [1,3],[2,6],[8,10],[15,18],
返回 [1,6],[8,10],[15,18].

解题思路

  判断 b 区间是否重叠 a 需要判断 b.start < a.end 。更新合并后的区间为 a.end = max(a.end , b.end)。

解题代码

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
/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector<Interval> merge(vector<Interval>& intervals) {
        if (intervals.size() <= 1) return intervals;
        sort(intervals.begin() , intervals.end() , [](Interval &a , Interval &b){
            return a.start < b.start;
        });
        vector<Interval> ret(0);
        ret.push_back(intervals[0]);
        for (auto &interval : intervals){
            if (interval.start > ret.back().end) ret.push_back(interval);
            else ret.back().end = max(ret.back().end , interval.end);
        }
        return ret;
    }
};
0%