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 | class Solution {
public:
vector<vector<int>> insert(vector<vector<int>> &intervals,
vector<int> &newInterval) {
vector<vector<int>> ans;
int newStart = newInterval[0];
int newEnd = newInterval[1];
int N = intervals.size();
int i = 0;
// step 1 : non-overlap left
for (; i < N && intervals[i][1] < newStart; i++)
ans.push_back(intervals[i]);
// step 2 : merge overlap interval
for (; i < N && intervals[i][0] <= newEnd; i++) {
newStart = min(newStart, intervals[i][0]);
newEnd = max(newEnd, intervals[i][1]);
}
ans.push_back({newStart, newEnd});
// step 3 : non-overlap right
for (; i < N; i++)
ans.push_back(intervals[i]);
return ans;
}
};
|