Insert Interval

You are given a set of non-overlapping intervals sorted by start time, where each intervals[i] = [start, end], plus a newInterval = [start, end]. Insert newInterval into the set, merging with any intervals it overlaps, and return the resulting set of non-overlapping intervals, still sorted by start time.

Intervals that touch at an endpoint are considered to overlap and should be merged.

Hints

· Stuck? Reveal one nudge at a time.

The given intervals are already sorted and disjoint — do you really need to sort again?

Split the intervals into three groups: entirely before the new one, overlapping it, entirely after.

Merge the overlapping group by taking the min start and max end, then emit one interval.

Common doubts

The input is already sorted and non-overlapping, so no sort is needed — a single left-to-right pass handles the before / merge / after phases in order.

Touching intervals overlap for this problem: an interval starting exactly at the new interval's end must be merged, so the comparison is inclusive.

Then the merge phase runs zero times and newInterval is emitted as its own interval between the before and after groups.

Interview follow-ups

· What an interviewer asks next.

Fall back to the general merge-intervals approach: add newInterval, sort by start, and merge — that's the O(n log n) brute force here.

Either apply the three-phase insert repeatedly, or collect them all and run a single sort-and-merge over everything.

Fun facts

This is 'Merge Intervals' with a shortcut: knowing the input is pre-sorted removes the sort and drops it to linear time.
The three-phase structure — skip, absorb, copy — is a common shape for one-pass interval algorithms.

Asked at

GoogleAmazonMetaMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
The new interval [2,5] overlaps [1,3], merging into [1,5]; [6,9] is untouched.

Example 2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
[4,8] overlaps [3,5], [6,7], and [8,10], merging them all into [3,10].

Constraints

- 0 <= intervals.length <= 10^4 - intervals is sorted by start and has no overlapping intervals - newInterval.length == 2 and start <= end

Because the intervals are already sorted and disjoint, you don't need to re-sort anything. Walk them once in three phases: copy the intervals that end before the new one, absorb every interval the new one touches into a single widening block, then copy the rest.

Prerequisites

Before you start

· Concepts used directly in the solution.

Merging intervals. Two intervals overlap (or touch) when one's start is <= the other's end; merging takes the min start and max end.

Sorted input. The given intervals are sorted by start and disjoint, which is what enables the single linear pass.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The input

“Are the given intervals already sorted and non-overlapping?”

Yes — sorted by start with no overlaps among them, so only the new interval can cause merges.

“Do touching intervals merge?”

Yes — an interval whose start equals the new interval's end still overlaps and merges.

Output

“Must the output stay sorted?”

Yes — return the merged set in start order (which the one-pass method preserves).

The ideal opening — say it like this

The intervals are already sorted and disjoint, so I'll do a single pass in three phases.

First copy everything ending before the new interval starts.

Then merge every interval that overlaps the new one into a single expanding interval, and finally copy the rest.

Understand the problem

Worked example — intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

before:  [1,2]                       (ends 2 < 4)
merge:   [3,5] [6,7] [8,10]  ->  new grows [4,8] -> [3,8] -> [3,8] -> [3,10]
after:   [12,16]
result:  [[1,2], [3,10], [12,16]]

Key observations

1Aha

Sorted input means three clean phases

The intervals ending before, overlapping, and starting after the new interval form three contiguous runs. A single left-to-right pass handles each in turn.

2Aha

Merging is min-start, max-end

Every overlapping interval is absorbed by taking the minimum start and maximum end seen so far — that single interval replaces the whole overlapping run.

3Aha

No sort needed

Since the input is already sorted and disjoint, the answer comes out sorted for free — an O(n) pass rather than O(n log n).

Brute force vs optimal

	Add + sort + merge	Three-phase scan
Idea	Append newInterval, sort all, merge overlaps	One pass: before, merge, after
Time	O(n log n)	O(n)
Space	O(n)	O(n) output

The sort-and-merge ignores that the input is already sorted; the three-phase scan exploits it for a linear pass. Full code is in the Approaches selector below.

Summary

Key takeaway

With sorted, disjoint intervals, insert in one pass: copy those ending before the new interval, merge everything it overlaps into one widening interval (min start, max end), then copy the rest. No re-sorting — O(n).

copy intervals with end < newStart
while interval.start <= newEnd:
    newStart = min(newStart, interval.start)
    newEnd   = max(newEnd,   interval.end)
emit [newStart, newEnd]
copy the remaining intervals