AlgoMaster Logo

Insert Interval

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

We have a sorted list of non-overlapping intervals, and we need to insert a new interval into it. The complication is that the new interval might overlap with one or more existing intervals, and when that happens, we merge them all into a single interval.

A timeline makes this concrete. The existing intervals are blocks of time already reserved, and the new interval is a block we want to add. If the new block overlaps existing reservations, they combine into one larger block. If it overlaps nothing, it slots into its sorted position untouched.

Because the intervals are already sorted, we can split the work into three groups: intervals that end before the new interval starts, intervals that overlap it, and intervals that start after it ends. The first and last groups stay unchanged. The middle group merges with the new interval.

Key Constraints:

  • intervals is sorted by start_i → The list is already in order, so a single left-to-right pass suffices. There is no need to sort.
  • intervals has no overlapping intervals → The existing list is already clean, so any overlap must involve the new interval. This is what makes the overlapping intervals contiguous.
  • 0 <= start_i <= end_i <= 10^5 → All values fit in a 32-bit integer with room to spare, so there is no overflow risk when comparing or taking min/max of boundaries.
  • 0 <= intervals.length <= 10^4 → The list can be empty, so the code must handle the case where the new interval is the only result.

Approach 1: Brute Force (Insert and Re-merge)

Intuition

One way to insert the interval is to ignore the existing order entirely. Add the new interval to the list, sort everything by start time, then merge any overlapping intervals in one pass. This is the standard merge-intervals routine with an insertion step at the front, and it works regardless of whether the input was sorted.

The cost is a sort over an already-sorted list, which is wasted work. It does make the logic easy to reason about, since the merge step handles every overlap case uniformly.

Algorithm

  1. Add newInterval to the intervals list.
  2. Sort the entire list by start time.
  3. Initialize a result list with the first interval.
  4. For each subsequent interval, check if it overlaps with the last interval in the result (i.e., its start is less than or equal to the last interval's end).
  5. If it overlaps, merge by updating the end of the last result interval to max(lastEnd, currentEnd).
  6. If it doesn't overlap, add it to the result as a new interval.
  7. Return the result.

Example Walkthrough

1Initial intervals: [[1,3],[6,9]], newInterval = [2,5]
[1, 3]
[6, 9]
19
1/6

Code

The sort is the only reason this is O(n log n), and the input is already sorted. The next approach drops the sort and finds the insertion point and handles merges in a single left-to-right pass, bringing the time down to O(n).

Approach 2: Linear Scan with Merge

Intuition

Because the intervals are already sorted by start time, the input falls into three contiguous groups, and we can process them in one pass.

Phase 1: All intervals that end before the new interval starts. These do not overlap the new interval, so we add them directly to the result.

Phase 2: All intervals that overlap the new interval. As we find each one, we merge it into the new interval by expanding its boundaries: take the minimum start and maximum end seen so far.

Phase 3: All intervals that start after the new interval ends. These come after it, so we add them directly to the result.

Each interval is examined once, and there is no sorting.

Algorithm

  1. Initialize an empty result list and an index i = 0.
  2. Phase 1 (Before): While i < n and intervals[i][1] < newInterval[0], add intervals[i] to the result and increment i. These intervals end before the new interval starts.
  3. Phase 2 (Merge): While i < n and intervals[i][0] <= newInterval[1], merge: set newInterval[0] = min(newInterval[0], intervals[i][0]) and newInterval[1] = max(newInterval[1], intervals[i][1]). Increment i.
  4. Add the (possibly merged) newInterval to the result.
  5. Phase 3 (After): While i < n, add the remaining intervals[i] to the result and increment i.
  6. Return the result.

Example Walkthrough

1Initialize: i=0, newInterval=[4,8], result=[]
[1, 2]
[3, 5]
[6, 7]
[8, 10]
[12, 16]
116
1/8

Code