LeetCode刷题实战56：合并区间
共 1417字，需浏览 3分钟
·
2020-10-06 01:43
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 合并区间，我们先来看题面：
https://leetcode-cn.com/problems/merge-intervals/
Given a collection of intervals, merge all overlapping intervals.
题意
样例
示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
解题
class Solution {
public:
static bool myCompare(Interval one, Interval two){
//以start为主次序递增
if (one.start == two.start){//当start相等的时候，才进行比较end
return one.end < two.start;
}
else {//否则直接比较start的大小关系
return one.start < two.start;
}
}
vectormerge(vector & intervals) {
sort(intervals.begin(), intervals.end(), myCompare);//按照自定义顺序进行排序
for (int i = 0; i < intervals.size(); ++i){//动态扫描
int begin = intervals[i].start;//基准begin
int end = intervals[i].end;//基准end
//因为排序的时候就保证了start为主次序递增，只要下一个的start小于上一个的end，就证明可以进行合并
while (i + 1 < intervals.size() && intervals[i + 1].start <= end){//如果能进行合并
end = max(intervals[i + 1].end, end);//更新
intervals.erase(intervals.begin() + i + 1);
}
intervals[i].end = end;//更新i的end
}
return intervals;
}
};
上期推文：