leetcode 56. 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].
思路：扫一遍即可。。
/* ***********************************************
Author :111qqz
Created Time :2017年04月11日 星期二 19时15分30秒
File Name :56.cpp
************************************************ */
/**
* 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:
1 int n;
2 static bool cmp(Interval A,Interval B)
3 {
4 return A.start<B.start;
5 }
6 vector<Interval> merge(vector<Interval>& pi) {
7 vector<Interval>res;
8 n = pi.size();
9 if (n==0) return res;
10 sort(pi.begin(),pi.end(),cmp);
11 int l = -1,r = -1;
12 for ( int i = 0 ; i < n ; i++)
13 {
14 if (l==-1&&r==-1)
15 {
16 l = pi[0].start;
17 r = pi[0].end;
18 continue;
19 }
20 if (pi[i].start<=r)
21 {
22 r = max(r,pi[i].end);
23 continue;
24 }
25 if (pi[i].start>r)
26 {
27 res.push_back(Interval(l,r));
28 l = pi[i].start;
29 r = pi[i].end;
30 continue;
31 }
32 }
33 //最后一组不要忘记
34 res.push_back(Interval(l,r));
35 int siz = res.size();
36 for ( int i = 0 ; i < siz ;i++) printf("%d ",res[i].start,res[i].end);
return res;
}
};