Problem Statement

Insert Interval

An interval is just a pair of numbers, a start and an end, like [2,5]. Think of it as a busy block of time on a calendar, say from 2 o'clock to 5 o'clock. You are given a list of these busy blocks, already sorted by start time, and none of them overlap each other. Then you get one new block to add. Your job is to slot it in, and if it bumps into any existing blocks (they share time), glue them together into one bigger block. The trick that makes this easy: because the list is already sorted, you can sweep through it left to right in three clean phases. First handle the blocks that come fully before the new one, then merge anything that touches it, then handle the blocks that come fully after.

mediumGreedyArrayIntervalsTime: O(n) · Space: O(n)

Signals to notice

insert a new interval into sorted non-overlapping intervalsmerge if overlappingthree phases

Brute force first

Add the interval, re-sort, then merge. Doesn't exploit the already-sorted structure. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

Three phases: (1) add all intervals that end before newInterval starts (no overlap). (2) Merge all overlapping intervals with newInterval. (3) Add all intervals that start after newInterval ends. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.

Trace it on `intervals=[[1,3],[6,9]], newInterval=[2,5]`

init: result=[], i=0, newInterval=[2,5]
Phase1 (end < 2): intervals[0][1]=3 not < 2 -> stop, nothing added, i=0
Phase2 (start <= 5): intervals[0][0]=1 <= 5 -> merge newInterval=[min(2,1),max(5,3)]=[1,5], i=1
Phase2: intervals[1][0]=6 not <= 5 -> stop; append newInterval -> result=[[1,5]]
Phase3 (add rest): append intervals[1]=[6,9] -> result=[[1,5],[6,9]], i=2
return [[1,5],[6,9]]

What must stay true

The intervals are already sorted and non-overlapping. The new interval can only overlap with a contiguous run of existing intervals — everything before and after is independent. When you keep that truth intact, each local choice supports the larger solution instead of fighting it.

Shape of the loop

result = []; i = 0
while i<n and intervals[i].end < new.start: result.add(intervals[i]); i++
while i<n and intervals[i].start <= new.end:
    new = [min(new.start,intervals[i].start), max(new.end,intervals[i].end)]; i++
result.add(new)
while i<n: result.add(intervals[i]); i++   # return result

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not merging transitively — the new interval might overlap with multiple existing intervals. Keep extending the merge while overlap exists. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Intervals Pattern