forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathnhistory.js
More file actions
29 lines (24 loc) · 755 Bytes
/
nhistory.js
File metadata and controls
29 lines (24 loc) · 755 Bytes
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
var insert = function (intervals, newInterval) {
let result = [];
let i = 0;
// 1. Add all intervals before the new interval
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
result.push(intervals[i]);
i++;
}
// 2. Merge all overlapping intervals with new interval
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.push(newInterval);
// 3. Add all intervals after the new interval
while (i < intervals.length && intervals[i][1] >= newInterval[0]) {
result.push(intervals[i]);
i++;
}
return result;
};
// TC = O(n)
// SC = O(n)