Insert Interval

Q: Why do infra roles meet this problem?

Adding a new maintenance window, change freeze or on-call shift to an existing sorted schedule is exactly this. It also appears when adding an IP range to a sorted, non-overlapping allocation table and coalescing adjacent blocks.

Q: What if touching intervals should stay separate?

Change the comparisons to strict: treat an interval as "before" when end <= newStart and as overlapping only when start < newEnd. Always confirm which rule the interviewer wants.

Q: Can I binary-search for the insert position?

You can find the first and last overlapping interval in O(log n), but building the output list still copies O(n) intervals, so the total stays O(n).

mediumIntervals Must-do

You get a list of intervals [start, end] that do not overlap and are sorted by start, plus one newInterval. Insert newInterval into the list so that the result is still sorted and still has no overlapping intervals, merging wherever necessary.

Intervals that share an endpoint count as overlapping, so [1, 3] and [3, 5] merge into [1, 5]. Return the resulting list.

Examples

Example 1

Input: intervals = [[1, 3], [6, 8], [10, 14]], newInterval = [7, 11]

Output: [[1, 3], [6, 14]]

Explanation: [7, 11] overlaps both [6, 8] and [10, 14], so all three become [6, 14].

Example 2

Input: intervals = [[2, 4], [9, 12]], newInterval = [5, 7]

Output: [[2, 4], [5, 7], [9, 12]]

Explanation: No overlap; the new interval just slots into the gap.

Hints

Approach

Walk the sorted list once in three phases.

Before: while the current interval ends before the new one starts (end < newStart), copy it to the result.
Overlap: while the current interval starts at or before the new one ends (start <= newEnd), it overlaps. Absorb it: newStart = min(newStart, start), newEnd = max(newEnd, end). Then append the widened new interval once.
After: copy every remaining interval.

Each interval is looked at once, so this is linear. The widened interval is appended even when nothing overlapped, which covers the "slot into a gap" case.

ComplexityTime O(n)Space O(n)

Python

class Solution:
    def insert(self, intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
        out = []
        i, n = 0, len(intervals)
        s, e = newInterval
        while i < n and intervals[i][1] < s:      # entirely before
            out.append(intervals[i])
            i += 1
        while i < n and intervals[i][0] <= e:     # overlapping: absorb
            s = min(s, intervals[i][0])
            e = max(e, intervals[i][1])
            i += 1
        out.append([s, e])
        out.extend(intervals[i:])                 # entirely after
        return out

Follow-up questions

Insert many new intervals, one at a time, into a structure that stays fast. What would you store them in?

Frequently asked questions

Adding a new maintenance window, change freeze or on-call shift to an existing sorted schedule is exactly this. It also appears when adding an IP range to a sorted, non-overlapping allocation table and coalescing adjacent blocks.

Change the comparisons to strict: treat an interval as "before" when end <= newStart and as overlapping only when start < newEnd. Always confirm which rule the interviewer wants.

You can find the first and last overlapping interval in O(log n), but building the output list still copies O(n) intervals, so the total stays O(n).

Problem statement