59. Merge Intervals

리트코드

• 겹치는 구간을 병합하라.

1. 정렬하여 병합

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        merged = []
        for i in sorted(intervals, key=lambda x: x[0]):
            if merged and i[0] <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], i[1])
            else:
                merged += i,
        
        return merged
        

• 이 문제를 풀기 위해서는 먼전 정렬을 수행한다.

  • 정렬 순서는 첫 번째 값을 기준으로 한다.

sorted(intervals, key=lambda x: x[0])

• 람다를 이용하면 첫 번째 값을 키로 이용하라는 지시를 할 수 있다.

  • 두 번째 값을 사용할 경우에는 당연히 x[1]로 지정하면 된다.

• 그렇게 했을 때 현재 아이템의 시작이 이전 아이템의 끝과 겹치게 되면 다음과 같이 최댓값을 기준으로 병합하는 형태로 계속 반복해 나간다.

  

  • 그림에서 (1,3)은 (2,6)과 병합되어 (1,6)이 되었다.

  • 만약 다음 아이템의 시작 값이 이전 아이템의 끝과 더 이상 겹치지 않게 된다면, 병합을 멈추고 다음과 같이 merged += i,를 이용해 새로운 아이템으로 추가한다.

    • ,는 중첩 리스트로 만들어 주는 역할을 한다.

    • 즉 대괄호 [ ]를 부여한 것과 동일한 역할을 한다.

    >>> a = [1]
    >>> b = [2, 3]
    >>> a += b,
    >>> a

    [1, [2, 3]]

• 이 방식의 시간 복잡도는 정렬에 소요되는 O(nlogn) 정도다.

• 나머지 리스트를 순회하는 작업은 선형 시간에 수행되므로, 상항은 마찬가지로 O( nlogn)이다.