[Leetcode][Python] 57. Insert Interval

리트코드 / 파이썬 / 57. Insert Interval

https://leetcode.com/problems/insert-interval/

 

Insert Interval - LeetCode

풀이 방법

Leetcode Description의 Example2로 설명해본다.

 

---

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

---

 

새로운 interval [4,8]이 기존 interval의 [3,5], [6,7], [8,10]와 겹치는 케이스다.

output을 보면, 겹치는 일부를 제외한 나머지 부분은 그대로인 것을 알 수 있다.

 

즉, 기존 interval과 겹치는 부분인 [3,5], [6,7], [8,10]을 제외하고

left: [1,2] / right: [12,16] 이 부분은 input과 변함이 없다. 

 

 

 

 

 

그림에서 left의 기준은 어떻게 될까? 

interval[1] < newInterval[0]인 것들이 차례로 추가된다. (해당 예시에서는 1개다.)

right도 비슷하게, interval[0] > newInterval[1]인 것들이 추가된다. (이것 역시 1개다.)

 

left, right을 제외한 나머지가 newInterval과 겹치는 것들인데,

비교 대상 interval의 0번째 value가 newInterval[0]보다 작으면 newInterval[0]을 업데이트 해주고,

비교 대상 interval의 1번째 value가 newInterval[1]보다 크면 newInterval[1]을 업데이트 해준다.

 

이를 소스코드로 표현하면,

mergedInterval[0] = min(mergedInterval[0], interval[0])
mergedInterval[1] = max(mergedInterval[1], interval[1])

(input value인 newInterval이 다른 interval과 비교되면서 업데이트되므로, mergeInterval이라고 했다.)

 

그림에서 보는 것과 같이 [3,5], [6,7], [8,10]과 newInterval [4,8]을 비교한 결과는 [3,10]이다. 

 

최종 결과는 [left] + mergedInterval + [right]을 한 것으로, [[1,2],[3,10],[12,16]] 가 된다.

 

소스 코드

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        https://leetcode.com/problems/insert-interval/
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        mergedInterval = newInterval
        left, right = [], []

        for interval in intervals:
            if interval[1] < mergedInterval[0]:
                left += interval,
            elif interval[0] > mergedInterval[1]:
                right += interval,
            else:
                mergedInterval[0] = min(mergedInterval[0], interval[0])
                mergedInterval[1] = max(mergedInterval[1], interval[1])

        return left + [mergedInterval] + right