Insert a new interval into a sorted list of non-overlapping intervals.
This problem follows the Linear Merge pattern, commonly found in the Intervals category. Recognizing this pattern is key to solving it efficiently in an interview setting.
Add all intervals before. Merge overlapping. Add all intervals after.
Three phases (before, merge, after) handle all cases cleanly — the merge phase extends the new interval's boundaries as it absorbs overlapping intervals.
result = []
i = 0
# Add intervals before newInterval
while i < len(intervals) and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
# Merge overlapping
while i < len(intervals) and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
# Add remaining
result.extend(intervals[i:])
return resultPractice Insert Interval and similar Intervals problems with flashcards. Build pattern recognition through active recall.
Practice this problem