[LeetCode] Insert Interval

57. Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times

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
class Solution {
public:
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
if(intervals.empty()) {
return vector<vector<int>>{newInterval};
} else if(intervals.front()[0] > newInterval[1]) {
intervals.insert(intervals.begin(), newInterval);
return intervals;
} else if(intervals.back()[1] < newInterval[0]) {
intervals.push_back(newInterval);
return intervals;
}

int startPos = intervals.size() - 1, endPos = intervals.size() - 1;
for(int i = 0; i < intervals.size(); i++) {
if(intervals[i][1] >= newInterval[0]) {
startPos = min(startPos, i);
}

if(intervals[i][0] > newInterval[1]) {
endPos = min(endPos, i - 1);
break;
}
}

intervals.insert(intervals.begin() + startPos, vector<int>{min(intervals[startPos][0], newInterval[0]), max(intervals[endPos][1], newInterval[1])});
intervals.erase(intervals.begin() + startPos + 1, intervals.begin() + endPos + 2);

return intervals;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2021/04/05/PS/LeetCode/insert-interval/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.