forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathEgonD3V.py
More file actions
66 lines (52 loc) ยท 2.02 KB
/
EgonD3V.py
File metadata and controls
66 lines (52 loc) ยท 2.02 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
58
59
60
61
62
63
64
65
66
from bisect import bisect_left
from typing import List
from unittest import TestCase, main
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
return self.solve(intervals, newInterval)
"""
Runtime: 1 ms (Beats 95.76%)
Time Complexity: O(n)
> intervals์ ์ ์ฒด๋ฅผ ์ ํ์ ์ผ๋ก ์กฐํํ๋ฏ๋ก O(n), ๊ทธ ์ธ์ append๋ฑ์ ์ฐ์ฐ๋ค์ O(1)์ด๋ฏ๋ก ๋ฌด์
Memory: 18.70 MB (Beats 99.60%)
Space Complexity: O(n)
> result์ ํฌ๊ธฐ๋ intervals์ newInterval์ด ํ๋๋ ๊ฒน์น์ง ์๋ ๊ฒฝ์ฐ, ์ต๋ n + 1์ด๋ฏ๋ก, O(n + 1) ~= O(n)
"""
def solve(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
if not intervals:
return [newInterval]
result = []
new_s, new_e = newInterval
for interval in intervals:
s, e = interval
if e < new_s:
result.append(interval)
elif new_e < s:
if new_s != -1 and new_e != -1:
result.append([new_s, new_e])
new_s = new_e = -1
result.append(interval)
else:
new_s = min(new_s, s)
new_e = max(new_e, e)
if new_s != -1 and new_e != -1:
result.append([new_s, new_e])
return result
class _LeetCodeTestCases(TestCase):
def test_1(self):
intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]]
newInterval = [4,8]
output = [[1,2],[3,10],[12,16]]
self.assertEqual(Solution().insert(intervals, newInterval), output)
def test_2(self):
intervals = [[1,2]]
newInterval = [3,4]
output = [[1,2], [3,4]]
self.assertEqual(Solution().insert(intervals, newInterval), output)
def test_3(self):
intervals = [[1,3], [5,6]]
newInterval = [4,5]
output = [[1,3], [4,6]]
self.assertEqual(Solution().insert(intervals, newInterval), output)
if __name__ == '__main__':
main()