Medium Linear Scan Intervals
In plain English: Insert a new time range into an already-sorted list of non-overlapping ranges, merging any overlaps.
Three phases: (1) add all intervals that come entirely before the new one, (2) merge all overlapping intervals with the new one, (3) add all intervals that come entirely after. Clean linear scan.
Prompt
Given a sorted list of non-overlapping intervals and a new interval, insert the new interval and merge if necessary. Return the result sorted.
Try to write it from scratch before scrolling down.
Solution
def insert(intervals, new):
result = []
i = 0
n = len(intervals)
# Phase 1: intervals entirely before new
while i < n and intervals[i][1] < new[0]:
result.append(intervals[i])
i += 1
# Phase 2: merge overlapping intervals
while i < n and intervals[i][0] <= new[1]:
new = [min(new[0], intervals[i][0]),
max(new[1], intervals[i][1])]
i += 1
result.append(new)
# Phase 3: intervals entirely after
while i < n:
result.append(intervals[i])
i += 1
return result
# Test: insert([[1,3],[6,9]], [2,5]) == [[1,5],[6,9]]
# Test: insert([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])
# == [[1,2],[3,10],[12,16]]