LeetCode - Insert Interval

Description

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

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].

겹치지 않는 정수 범위 배열이 범위의 시작을 기준으로 정렬된 상태로 주어졌을 때 새롭게 주어진 범위를 원래 배열에 삽입하는 문제.
만약 오버랩 되는 부분이 있으면 기존 범위를 merge한다.

풀이

첫번째 시도

정렬되어 있다는 점에서 착안해서 이분탐색을 생각해보았다.(결과적으론 뻘짓)

먼저 최종적으로 삽입될 범위에 대한 배열과 병합되어야 할 배열 요소들의 시작과 끝을 담을 변수를 선언해두었다.

toMerge = [None, None]
merge_start = -1
merge_end = -1

그리고 범위의 시작과 끝에 대해 이분탐색을 통해 각각 들어가야 될 부분을 찾았다.

low = 0
high = n

while low < high:
  mid = int((low + high) / 2)
  s, e = intervals[mid]

  if s <= start and start <= e:
    merge_start = mid
    toMerge[0] = s
    if end <= e:
      return intervals
      break
  elif start < s:
      high = mid
  elif start > e:
      low = mid + 1

if merge_start < 0:
  merge_start = low
  toMerge[0] = start

범위 끝에 대해서도 마찬가지 작업을 하고 최종적으로 완성된 범위를 기존 범위 배열에 삽입해준다.

intervals[merge_start:merge_end + 1] = [toMerge]
return intervals

결과는 충격적이게도 하위권이었다 ㅋㅋㅋㅋㅋㅋ

다른 사람은 어떻게 풀었나?

def insert(self, intervals, newInterval):
  n = newInterval
  result = []

  for i, range in enumerate(intervals):
    start, end = range
    if end < n[0]:
      result.append(range)
    elif start > n[1]:
      result.append(newInterval)
      return result + intervals[i:]
    else:
      n[0] = min(start, n[0])
      n[1] = max(end, n[1])

result.append(n)
return result

띠용