forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathgwbaik9717.js
More file actions
57 lines (44 loc) · 1.08 KB
/
gwbaik9717.js
File metadata and controls
57 lines (44 loc) · 1.08 KB
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// Time complexity: O(n)
// Space complexity: O(n)
/**
* @param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}
*/
var insert = function (intervals, newInterval) {
// 1. Insert newInterval
const candidates = [];
let inserted = false;
if (intervals.length === 0) {
candidates.push(newInterval);
}
for (const [start, end] of intervals) {
const [newStart, newEnd] = newInterval;
if (!inserted) {
if (newStart <= start) {
candidates.push([newStart, newEnd]);
inserted = true;
}
}
candidates.push([start, end]);
}
if (!inserted) {
candidates.push(newInterval);
}
// 2. Merge if needed
const answer = [];
for (const [start, end] of candidates) {
if (answer.length === 0) {
answer.push([start, end]);
continue;
}
const [compareStart, compareEnd] = answer.at(-1);
if (compareEnd >= start) {
answer.pop();
answer.push([Math.min(start, compareStart), Math.max(end, compareEnd)]);
continue;
}
answer.push([start, end]);
}
return answer;
};