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) {}
* };
*/
bool cmp(const Interval &a,const Interval &b)
{
return a.start < b.start;
}
class Solution
{
public:
vector<Interval> merge(vector<Interval>& intervals)
{
vector<Interval> ans;
if(intervals.size() == 0)
return ans;
sort(intervals.begin(), intervals.end(), cmp);
int b, e;
for(int i=0; i<intervals.size(); ++ i)
{
if(i == 0)
b = intervals[i].start, e = intervals[i].end;
else
{
if(intervals[i].start > e)
{
ans.push_back(Interval(b, e));
b = intervals[i].start, e = intervals[i].end;
}
else
{
if(intervals[i].end > e)
e = intervals[i].end;
}
}
}
ans.push_back(Interval(b, e));
return ans;
}
};