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].
思路：扫一遍即可。。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月11日 星期二 19时15分30秒
4File Name :56.cpp
5************************************************ */
6/**
7
8 * Definition for an interval.
9
10 * struct Interval {
11
12 * int start;
13
14 * int end;
15
16 * Interval() : start(0), end(0) {}
17
18 * Interval(int s, int e) : start(s), end(e) {}
19
20 * };
21
22 */
23
24class Solution {
25
26public:
27
28 int n;
29 static bool cmp(Interval A,Interval B)
30 {
31 return A.start<B.start;
32 }
33 vector<Interval> merge(vector<Interval>& pi) {
34 vector<Interval>res;
35 n = pi.size();
36 if (n==0) return res;
37 sort(pi.begin(),pi.end(),cmp);
38 int l = -1,r = -1;
39 for ( int i = 0 ; i < n ; i++)
40 {
41 if (l==-1&&r==-1)
42 {
43 l = pi[0].start;
44 r = pi[0].end;
45 continue;
46 }
47 if (pi[i].start<=r)
48 {
49 r = max(r,pi[i].end);
50 continue;
51 }
52 if (pi[i].start>r)
53 {
54 res.push_back(Interval(l,r));
55 l = pi[i].start;
56 r = pi[i].end;
57 continue;
58 }
59 }
60 //最后一组不要忘记
61 res.push_back(Interval(l,r));
62 int siz = res.size();
63 for ( int i = 0 ; i < siz ;i++) printf("%d ",res[i].start,res[i].end);
64
65
66 return res;
67
68 }
69
70};