forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmike2ox.ts
More file actions
29 lines (27 loc) ยท 1007 Bytes
/
mike2ox.ts
File metadata and controls
29 lines (27 loc) ยท 1007 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
/**
* Source: https://leetcode.com/problems/insert-interval/
* ํ์ด๋ฐฉ๋ฒ: ๋ฏธ๋ฆฌ ์ ๋ ฌ ํ ๋ ๋ถ๋ถ๋ง ๋น๊ตํ๋ฉด์ ๊ฐฑ์ ์ํค๊ธฐ
* ์๊ฐ๋ณต์ก๋: O(nlogn) - ์ ๋ ฌ๋๋ฌธ์
* ๊ณต๊ฐ๋ณต์ก๋: O(n)
*
* ํต๊ณผ์๊ฐ
* - ์ต์ด: 40๋ถ
*/
function insert(intervals: number[][], newInterval: number[]): number[][] {
const mergedIntervals = [...intervals, newInterval];
const result: number[][] = [];
mergedIntervals.sort((a, b) => a[0] - b[0]);
for (const interval of mergedIntervals) {
// ๊ฒฐ๊ณผ ๋ฐฐ์ด์ด ๋น์ด์๊ฑฐ๋ ํ์ฌ ๊ตฌ๊ฐ์ด ๋ง์ง๋ง ๊ตฌ๊ฐ๊ณผ ๊ฒน์น์ง ์๋ ๊ฒฝ์ฐ
if (result.length === 0 || interval[0] > result[result.length - 1][1]) {
result.push(interval);
} else {
// ๊ฒฐ๊ณผ๋ฌผ์ ๋ง์ง๋ง ๊ตฌ๊ฐ์ ํฐ๊ฐ ๋ฒ์์ ํ์ฌ ๊ตฌ๊ฐ์ ํฐ๊ฐ ๋ฒ์๋ฅผ ๋น๊ตํ ํฐ ๊ฐ์ผ๋ก ๋์ฒดํ๊ธฐ
result[result.length - 1][1] = Math.max(
result[result.length - 1][1],
interval[1]
);
}
}
return result;
}