HardIntervals

Insert Interval

Insert interval into sorted list

Solution Approach

Add non-overlapping intervals before, merge overlapping ones, add remaining after.

Implementation

def insert(intervals, newInterval):
    result = []
    i = 0
    
    while i < len(intervals) and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
    
    while i < len(intervals) and intervals[i][0] <= newInterval[1]:
        newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
        i += 1
    
    result.append(newInterval)
    result.extend(intervals[i:])
    return result

Complexity Analysis

Time Complexity

O(n log n)

Space Complexity

O(1)

Key Learning Points

Sort by start timeCompare overlapsTrack merged result