문제 설명

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

전체 코드

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        
        answer=[]
        
        intervals.sort(key=lambda x: x[0])
        standard=intervals[0]
        
        for i in range(1,len(intervals)):
            a,b=standard
            c,d=intervals[i]
            
            if b>=c:
                standard=[a,max(b,d)]
            else:
                answer.append((standard[0],standard[1]))
                standard=[c,d]
                
        answer.append(standard)
        
        return answer

해설

먼저 시작점, 즉 interval의 첫 번째 값을 기준으로 정렬해보자. (힌트 보긴 했음 ㅎㅎ)

여기서 (a,b), (c,d) ....로 정렬이 되있다고 해보자. 확실한 것은 a<=c와 a<=b, c<=d다.

그런데 오버랩되려면 어떻게 해야 될까?
바로, (a,b)와 (c,d)를 기준으로 반드시 b>=c여야 오버랩이 된다.

그런데 다음 두 가지 사례를 고려해야 한다.
예를 들어 (1,3), (2,6)을 오버랩하면 (1,6)이 된다.
그리고 (1,9), (4,6)을 오버랩하면 (1,9)가 된다.

즉, 시작점을 기준으로 정렬했을 때 (a,b), (c,d)가 있다면 a<=c이고, b>=c인 경우 (a,max(b,d))를 성립함을 알 수 있다.