[Leetcode] 56. Merge Intervals

문제 바로가기

Time Complexity: O(nlogn) - sort
Space Complexity: O(n)

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals = sorted(intervals)
        result = list()
        cur = intervals[0][:]
        
        for start, end in intervals[1:]:
            if start <= cur[1]:  # overlapping intervals
                cur[1] = max(cur[1], end)
            else:  # non-overlapping intervals
                result.append(cur)
                cur = [start, end]
        result.append(cur)
        
        return result