[LEETCODE] 56: Merge Intervals(Python)

Merge Intervals - LeetCode

문제 설명

나의 풀이

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        intervals.sort()

        stack=[]
        for i in intervals:
            if len(stack)==0:
                stack.append(i)
            else:
                if stack[-1][1]>=i[0]:
                    stack[-1]=[stack[-1][0],max(stack[-1][1],i[1])]
                else:
                    stack.append(i)
        return stack

먼저 간격들을 정렬한 뒤 스택에 넣어가면서 겹치는 구간이 있는지 확인한다. 정렬을 해 주면 연속된 구간만 겹칠 수 있다는 점을 보장한다.

시간복잡도

정렬에 O(nlogn)이 걸린다.