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; } };