56. Merge Intervals (Array, Sorting)

링크 - https://leetcode.com/problems/merge-intervals/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

이 문제는 Sorting으로 풀 수 있다.

 

먼저 list를 각 원소의 첫 번째 값을 기준으로 sorting한다. (유용한 파이썬 내장함수가 있는데, sorted(list, key=lambda x:x[0])를 쓰면 된다.) 그 다음, 첫번째 원소부터 시작해서 다음 비교하는 원소들의 두 번째 값을 비교한다. 

예를 들어, (1,4)와 (3,5)는 4와 3을 비교해서 4가 3보다 크거나 같으므로 두개의 interval들은 합칠 수 있다. 따라서 4와 5중 큰 값인 5를 사용하여 (1,5)로 통합이 가능하다. 

만약 첫번째 원소가 다음 비교하는 첫 번째 원소보다 작으면, 결과 리스트에 append한다. 

Code

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ans = []
        sorted_intervals = sorted(intervals, key=lambda x: x[0])
        cur_i = None
        for i in sorted_intervals:
            if cur_i is None:
                cur_i = i
            else:
                if cur_i[1] >= i[0]:
                    cur_i[1] = max(cur_i[1], i[1])
                else:
                    ans.append(cur_i)
                    cur_i = i
        ans.append(cur_i)
        return ans
        
# Different codes but same algorithm
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        intervals.sort(key=lambda x: x[0])

        merged = []
        for interval in intervals:
            # if the list of merged intervals is empty or if the current
            # interval does not overlap with the previous, simply append it.
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # otherwise, there is overlap, so we merge the current and previous
                # intervals.
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

Complexity

Time Complexity: O(nlogn) sorting이 작동하고 for문이 linear하게 동작하므로, nlogn이 걸리는 sorting에 지배를 받는다.

Space Complexity: O(logn) or O(n) 만약 intervals를 in-place로 sorting하면 sorting에 필요한 O(logn)말고는 따로 필요한 space는 없다. 만약 intervals를 따로 저장하면 O(n)의 저장공간이 필요하다.