23
08/2015
[LeetCode] Merge Intervals
Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
解题思路：
数组区域合并。
首先将原数组按照左边界排序，然后扫描数组。每次比较时，只需要与已扫描数组最后一个元素比较是否有重合区域。若有重合区域，则更改最后已扫描数组的最后一个元素的右边界，若无重合区域，则将新扫描的数组插入到已扫描的数组中。
注意自定义排序，可以用库排序，然后自定义比较元素即可。
/**
* 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) {
std::sort(intervals.begin(), intervals.end(), comp);
vector<Interval> result;
int len = intervals.size();
for(int i=0; i<len; i++){
if(result.size() == 0 || !isOver(result[result.size() - 1], intervals[i])){
result.push_back(intervals[i]);
}else{
//result[result.size() - 1].start = min(result[result.size() - 1].start, intervals[i].start);
result[result.size() - 1].end = max(result[result.size() - 1].end, intervals[i].end);
}
}
return result;
}
static bool comp(Interval& interval1, Interval& interval2){
return interval1.start < interval2.start;
}
bool isOver(Interval& interval1, Interval& interval2){
return interval1.start <= interval2.end && interval1.end>=interval2.start;
}
};转载请注明：康瑞部落 » [LeetCode] Merge Intervals
0 条评论