작심삼일

[LeetCode] 56 | Merge Intervals | Python 본문

스터디/코테

[LeetCode] 56 | Merge Intervals | Python

yun_s 2021. 12. 27. 10:01
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
반응형
Comments