7
7
* Interval(int s, int e) : start(s), end(e) {}
8
8
* };
9
9
*/
10
-
11
- bool compare (const Interval& lhs, const Interval& rhs) {
12
- if (lhs.start == rhs.start )
13
- return lhs.end < rhs.end ;
14
- return lhs.start < rhs.start ;
10
+
11
+ inline bool operator < (const Interval& x, const Interval& y) {
12
+ if (x.start == y.start ) {
13
+ return x.end < y.end ;
14
+ }
15
+ return x.start < y.start ;
15
16
}
16
17
17
18
class Solution {
18
19
public:
19
- vector<Interval> merge (vector<Interval>& intervals) {
20
- // Start typing your C/C++ solution below
21
- // DO NOT write int main() function
22
-
23
- if (intervals.empty ()) return vector<Interval>();
24
-
25
- sort (intervals.begin (), intervals.end (), compare);
26
-
27
- vector<Interval> merged_interval;
28
- merged_interval.push_back (intervals[0 ]);
29
-
20
+ vector<Interval> merge (vector<Interval> &intervals) {
21
+ vector<Interval> result;
22
+ if (intervals.empty ()) {
23
+ return result;
24
+ }
25
+ sort (intervals.begin (), intervals.end ());
26
+ result.push_back (intervals[0 ]);
30
27
for (int i = 1 ; i < intervals.size (); i++) {
31
- int start = merged_interval[merged_interval.size ()-1 ].start ;
32
- int end = merged_interval[merged_interval.size ()-1 ].end ;
33
- if (intervals[i].start <= end) {
34
- end = max (end, intervals[i].end );
35
- merged_interval.pop_back ();
36
- merged_interval.push_back (Interval (start, end));
37
- }
38
- else {
39
- merged_interval.push_back (intervals[i]);
28
+ Interval& back = result.back ();
29
+ if (back.end >= intervals[i].start ) {
30
+ back.end = max (back.end , intervals[i].end );
31
+ } else {
32
+ result.push_back (intervals[i]);
40
33
}
41
34
}
42
- return merged_interval ;
35
+ return result ;
43
36
}
44
- };
37
+ };
0 commit comments