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