[LeetCode] 56 | Merge Intervals | Python

---

문제 링크: 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