리트코드 56번 Merge Intervals (python)

Problem

https://leetcode.com/problems/merge-intervals/description/

Solution

내 풀이

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        answer = [intervals[0]]
        for left, right in intervals[1:]:
            prev_left, prev_right = answer.pop()
            if left <= prev_right:
                answer.append([prev_left, max(right, prev_right)])
            else:
                answer.append([prev_left, prev_right])
                answer.append([left, right])

        return answer

정렬한 뒤 이전 범위의 end 값이 현재 범위의 start 값보다 크거나 같다면 overlap이 발생한다.

이 경우 범위를 병합하여 넣어주었다. 이때 prev_right가 right보다 클 수 있다.
ex. [1, 4], [2,3] ⇒ [1,4]

Reference

파이썬 알고리즘 인터뷰 59번