greentea31's Note

https://leetcode.com/problems/merge-intervals/

풀이 과정

수직선 간의 주어진 구간에서, 겹치는 구간은 합병하는 문제이다.

위의 예시는 1~3 2~6은 겹치는 부분이니 1~6으로 합병한 예시임을 확인할 수 있다.

intervals을 리스트 내의 첫번째 원소를 기준으로 정렬해준 뒤, 각 구간의 현재 시작, 끝점과 이전 시작, 끝점을 비교하면서 이전 끝점이 현재 시작점보다 크면 합병을 해주는 방식으로 진행하였다. 합병 도중 이전 끝점이 현재 끝점보다 크면 합병 구간이 현재 끝점으로 당겨지는 경우가 없도록 예외 처리를 해주어야 한다.

소스 코드

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:x[0])
        prev_start, prev_end = intervals[0][0], intervals[0][1]
        answer = []
        
        for start, end in intervals:
            if prev_end >= end:
                continue
            if prev_end >= start:
                prev_end = end
                continue
            else:
                answer.append([prev_start, prev_end])
                prev_start, prev_end = start, end
        
        answer.append([prev_start, prev_end])
        
        return answer