Type:medium
Given a collection of intervals, merge all overlapping intervals.
Example 1:
Input:[[1,3],[2,6],[8,10],[15,18]]Output:[[1,6],[8,10],[15,18]]Explanation:Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
给定一个 vector<vector<int>> 型,要求输出的时候删去覆盖区间,如[1,3],[2,6]合并为[1,6]。
首先定义一个comp函数,输入要求为静态变量,返回值按照每个vector首数值排序。可以将此排序条件写入sort函数中。在排好序后,顺序读取每个vector,若下一个vector首数值小于上一个vector尾数值,则合并两个vector,尾数值取两者中更大的尾数值。
class Solution {
public:
static bool comp(const vector<int> a, const vector<int> b){
return (a[0] < b[0]);
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> ret;
if(intervals.empty()) return ret;
sort(intervals.begin(), intervals.end(), comp);
ret.push_back(intervals[0]);
for(int i=1; i<intervals.size(); i++){
if(ret.back()[1] >= intervals[i][0]){
ret.back()[1] = max(ret.back()[1], intervals[i][1]);
}else ret.push_back(intervals[i]);
}
return ret;
}
};