57. Insert Interval

[zeikar]

Problem link

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

Problem Summary

구간들이 주어질 때 새로운 구간을 추가하는 문제. 구간들은 겹칠 경우 머지되어야 한다.

Solution

약간 그리디 느낌?
겹치지 않은 경우는 그냥 결과 배열에 넣으면 되고 겹치는 경우는 left는 겹치는 구간들의 최소, right는 겹치는 구간들의 최대로 해서 추가하면 된다.

좀 지저분하게 짜긴 했지만 결과도 맞게 나오고 O(n)이라 별 상관 없다.

Source Code

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        resleft, resright = [], []
        [newLeft, newRight] = newInterval
        overlapLeft, overlapRight = newLeft, newRight

        for interval in intervals:
            [left, right] = interval

            if right < newLeft:
                resleft.append(interval)
            elif left > newRight:
                resright.append(interval)
            else:            
                overlapLeft = min(overlapLeft, left)
                overlapRight = max(overlapRight, right)
        
        resleft.append([overlapLeft, overlapRight])
        resleft.extend(resright)
        return resleft