Insert an interval, then output the merged result.
I took a shortcut here by directly reusing the merge function from the previous problem.
However, the problem states the intervals are already sorted, so the time complexity could be reduced to O(n).
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
| int cmp(Interval a, Interval b) {
if (a.start == b.start)
return a.end < b.end;
return a.start < b.start;
}
class Solution {
public:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
intervals.push_back(newInterval);
return merge(intervals);
}
private:
vector<Interval> merge(vector<Interval> &intervals) {
sort(intervals.begin(), intervals.end(), cmp);
vector<Interval> ans;
ans.clear();
if (intervals.size() <= 0) return ans;
Interval item = intervals[0];
for (int i = 1; i < intervals.size(); i++) {
if (item.end < intervals[i].start) {
ans.push_back(item);
item = intervals[i];
} else {
if (item.end < intervals[i].end)
item.end = intervals[i].end;
}
}
ans.push_back(item);
return ans;
}
};
|