LeetCode - 56. Merge Intervals (python)

https://leetcode.com/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-interview-150

• 난이도: medium
• 알고리즘: Intervals

접근방법

• [start, end]로 구성된 intervals를 sorted 함수를 통해 start 오름차순, end 오름차순으로 정렬
• 정렬된 intervals를 순회하며 현재 인덱스의 end와 다음 인덱스의 start를 비교
• 현재 인덱스의 end가 더 클 경우 현재 인덱스의 end와 다음 인덱스의 end 중 더 큰 것을 현재의 end로 갱신하고 intervals에서 다음 인덱스를 삭제한다
• 갱신된 intervals를 반환한다

소스코드

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        n = len(intervals)
        if n == 1:
            return [intervals[0]]
        
        intervals = sorted(intervals)

        i = 0
        while i < len(intervals):
            while i < len(intervals) - 1 and intervals[i][1] >= intervals[i + 1][0]:
                intervals[i][1] = max(intervals[i][1], intervals[i + 1][1])
                intervals.pop(i + 1)
                       
            i += 1

        return intervals