[리트코드] 56. Merge Intervals

581. Shortest Unsorted Continuous Subarray

문제

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

제한사항

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

풀이

각 interval을 merge해서 최종 시작점과 끝 점을 리턴해야하므로 시작점으로 정렬한다.

앞의 interval과 다음 시작점을 비교한다.

• merge가 가능하다면 -> merge end를 비교해서 더 큰 값으로 업데이트한다.
• 불가능하다면 옆에 새로운 interval을 만든다.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        result = []
        cnt = 0
        
        for start, end in intervals:
            if result and result[-1][1] >= start:# merge 될 때
                result[-1][1] = max(result[-1][1], end)
            else:# 옆에 붙일 때
                result.append([start, end])
    
        return result