8000 2 · zwxalgorithm/leetcode-1@b6c6b31 · GitHub
[go: up one dir, main page]

Skip to content

Commit b6c6b31

Browse files
committed
2
1 parent b34e422 commit b6c6b31

File tree

1 file changed

+20
-27
lines changed

1 file changed

+20
-27
lines changed

MergeIntervals/MergeIntervals.cpp

Lines changed: 20 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -7,38 +7,31 @@
77
* Interval(int s, int e) : start(s), end(e) {}
88
* };
99
*/
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;
1516
}
1617

1718
class Solution {
1819
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]);
3027
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]);
4033
}
4134
}
42-
return merged_interval;
35+
return result;
4336
}
44-
};
37+
};

0 commit comments

Comments
 (0)
0