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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50 |
/** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */struct
cmp{ bool
operator()(Interval a,Interval b){ return
a.start < b.start ; } } comp;class
Solution {public: vector<Interval> merge(vector<Interval> &intervals) { sort(intervals.begin(),intervals.end(),comp); int
size = intervals.size(); vector<Interval> re; if(intervals.size()==0)return
re; Interval temp; int
flag = 0; for(int
i = 0 ; i < size ;i++) { if(intervals[i].start >temp.end || flag ==0) { if(flag ==0) { flag =1; temp.start = intervals[i].start; temp.end = intervals[i].end; } else { re.push_back(temp); temp.start =intervals[i].start; temp.end =intervals[i].end; } } else
if(intervals[i].start <= temp.end) { if(temp.end < intervals[i].end)temp.end = intervals[i].end; } } re.push_back(temp); return
re; }}; |
Merge Intervals,布布扣,bubuko.com
原文：http://www.cnblogs.com/pengyu2003/p/3619190.html