반응형
Notice
Recent Posts
Recent Comments
- Today
- Total
작심삼일
[LeetCode] 56 | Merge Intervals | Python 본문
728x90
반응형
문제 링크: https://leetcode.com/problems/merge-intervals/
문제
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
조건
- 1 <= intervals.length <= $10^4$
- intervals[i].length == 2
- 0 <= starti <= endi <= $10^4$
내 풀이
입력의 조건이 $10^4$까지이므로 그에 해당하는 배열(check)을 만든다.
한 구간이 들어올 때마다 해당하는 자리에 입력한다. (ex. [1, 5]가 들어오면, check[1] = 5)
이때, 겹치는 구간을 처리하기 위해 max를 사용한다. (ex. [1,3], [1,5]가 들어오면, check[1]의 값은 $-1 \rightarrow 3 \rightarrow 5$로 바뀐다. 만약 [1,5], [1,3]순서로 들어와도 max때문에 check[1] = 5가 된다.)
모든 구간에 대해 배열을 입력했다면, 이제 정답을 출력하면 된다.
코드
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
check = [-1 for _ in range(10002)]
ans = []
for interval in intervals:
check[interval[0]] = max(check[interval[0]], interval[1])
s, e = -1, -1
for x in range(0, 10002):
if check[x] > -1 and s == -1:
s, e = x, check[x]
elif check[x] > -1 and s > -1:
e = max(e, check[x])
if x == e:
ans.append([s, e])
s, e = -1, -1
return ans
728x90
반응형
'스터디 > 코테' 카테고리의 다른 글
[LeetCode] 116 | Populating Next Right Pointers in Each Node | Python (0) | 2021.12.29 |
---|---|
[백준] 2638번 | 치즈 | (0) | 2021.12.27 |
[LeetCode] 476 | Number Complement | Python (0) | 2021.12.27 |
[백준] 2636번 | 치즈 | C++ (0) | 2021.12.23 |
[LeetCode] 210 | Course Schedule II | Python (0) | 2021.12.23 |
Comments