In Simple Words: 1. Add all intervals ending before newInterval starts. 2. Merge all overlapping intervals into newInterval by expanding its [min(start), max(end)]. 3. Add merged newInterval and append remaining subsequent intervals. - ...

Q18: Insert Interval. - DSA Patterns (Multi-Lang)

In Simple Words:

Add all intervals ending before newInterval starts.
Merge all overlapping intervals into newInterval by expanding its [min(start), max(end)].
Add merged newInterval and append remaining subsequent intervals.

Time: $O(N)$ | Space: $O(N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
    res = []
    i = 0
    n = len(intervals)
    # Add non-overlapping intervals prior
    while i < n and intervals[i][1] < newInterval[0]:
        res.append(intervals[i]); i += 1
    # Merge overlapping intervals
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    res.append(newInterval)
    # Append trailing intervals
    while i < n:
        res.append(intervals[i]); i += 1
    return res