skip to content

How do you insert one new interval into an already-merged, sorted list in one pass?

level: middleimportance: should knowfreq 55%

answer

  1. the stored list is already sorted and disjoint
  2. three phases, one scan
  3. before, overlapping, after
  4. widen with min start and max end
  5. compare against the updated end each step

basics

~20 s

Scan once in three phases: copy every interval ending before the new one starts, absorb each interval that reaches it by widening the new one to the smallest start and largest end, then copy the remainder. That is linear with no re-sort.

solid answer

~50 s

Exploit the invariant the stored list already has — sorted and pairwise disjoint — instead of appending and re-merging. One scan, three phases. **Phase one:** every existing interval that ends before the new one starts is untouched; copy it out. **Phase two:** every interval that still starts at or before the (growing) new end is absorbed — widen the new interval with `start = min(start, a[i].start)` and `end = max(end, a[i].end)`; because the stored list is disjoint, these absorbed intervals form one contiguous run. Emit the widened interval once the run ends. **Phase three:** copy the tail unchanged. Cost is `O(n)` time versus `O(n log n)` for append-and-re-sort, and the output preserves the sorted-disjoint invariant. Phase one's boundary can be a binary search when the list is long and the insert lands late, though rewriting the tail keeps the array form linear anyway.

code

pseudocode · 15 lines
pseudocode
i = 0
n = length(a)
out = empty list
while i < n and a[i].end < new.start
    append a[i] to out
    i = i + 1
while i < n and a[i].start <= new.end
    new.start = min(new.start, a[i].start)
    new.end = max(new.end, a[i].end)
    i = i + 1
append new to out
while i < n
    append a[i] to out
    i = i + 1
return out

go deeper

for a junior

Recall the three phases in order: copy what ends before, absorb what reaches, copy the rest. Know that the stored list being sorted and disjoint is what makes one pass enough.

for a middle

Explain why the absorbed intervals must be contiguous, and why the overlap test compares against the widened end rather than the original. Give the O(n) versus O(n log n) contrast with re-merging.

for a senior

Show judgment about arrival patterns: one-at-a-time splices for streaming inserts, a single batch re-merge for bulk import, with the O(mn) versus O((n+m) log(n+m)) reasoning behind the switch.

for a principal

Own the invariant as a contract: who guarantees the stored list stays sorted and disjoint, where that is enforced, and what it costs to keep it true under concurrent writers versus rebuilding on read.

## The invariant you are inheriting A merged interval list is not just a list — it carries two properties: the intervals are sorted by start, and they are pairwise disjoint (no two of them touch or overlap; if they did, the merge would have collapsed them). Adding one new range is a chance to exploit both. The lazy option is to append the new range and re-run the full merge, which sorts `n + 1` intervals for `O(n log n)`. The one-pass splice does the same job in `O(n)` and, more importantly, is easier to reason about: it re-establishes the same two properties directly. ## The three phases **Phase one — the untouched prefix.** Walk while the existing interval ends strictly before the new interval starts. These intervals cannot interact with the new one, they are already in order, and they are copied out verbatim. The loop stops at the first interval that reaches the new one. **Phase two — the absorbed run.** Walk while the existing interval starts at or before the new interval's *current* end, widening as you go: the new start becomes the minimum of the two starts, the new end the maximum of the two ends. Two details matter here. - The `min` on the start is needed only once in practice — the first absorbed interval may begin before the new one — but writing it unconditionally is the same shape as the merge's `max` on the end and removes a special case. - The comparison must be against the **updated** end, not the original. That is what allows a chain: a new range spanning a busy morning can swallow four stored slots in sequence. Because the stored list is disjoint, the absorbed intervals are necessarily contiguous in the list: once you find one that starts after the new end, every subsequent one starts later still. So phase two terminates the run for good, and the widened interval is emitted exactly once. **Phase three — the untouched suffix.** Everything remaining starts after the widened end and is copied verbatim. What comes out is sorted (prefix, then the widened interval, then a suffix that starts later) and disjoint (the prefix ends before the widened start, the suffix starts after the widened end). The invariant is restored, so the next insert can use the same routine. ## Costs, and where the log factor can and cannot help The scan is `O(n)` time; output space is `O(n)`, or `O(1)` extra if you rewrite in place and shift. Compare with append-and-re-merge: `O(n log n)` and a fresh allocation. For a single insert the linear splice wins. A tempting refinement is to binary search for the first interval that reaches the new range — the list is sorted, so that boundary is found in `O(log n)`. It genuinely helps when the structure supports cheap splicing in the middle. In a flat array form it does not change the asymptotics, because the elements after the insertion point still have to shift or be copied, which is `O(n)` regardless. Do not claim `O(log n)` for an insert into an array-backed list; the search is logarithmic, the rewrite is linear. The other refinement is knowing when *not* to insert one at a time. Adding `m` new ranges one by one is `O(mn)`. Concatenating all `m`, sorting once and re-merging is `O((n + m) log(n + m))`, which is far better once `m` grows. The single-insert splice is for the streaming case — one new booking arriving at a time against a maintained strip; the batch re-merge is for bulk import. Choosing between them is a question about the arrival pattern, not about the algorithms. ## Boundary and edge cases to state out loud - **Empty stored list:** phases one and two do nothing, the new interval is emitted alone. Falls out of the loops with no special case. - **New range before everything, or after everything:** phase one or phase three does all the work; again no special case. - **New range contained in an existing one:** phase two absorbs that interval; `min` and `max` leave the widened range equal to the stored one, and the output is unchanged in content. - **Touching boundaries:** whether `a[i].end < new.start` or `<=` is right depends on your interval convention — settle that before writing the comparison, because it decides whether an adjacent booking merges or stays separate. - **Zero-length or reversed ranges:** an input where end precedes start will corrupt the run detection; validate at the boundary rather than inside the loop.

  • Why not just append the new range and re-run the full merge?
    It works but throws away the invariant you already paid for. Re-merging sorts `n + 1` intervals for `O(n log n)` and reallocates, while the splice is one `O(n)` scan that re-establishes sorted-and-disjoint directly. The re-merge only becomes the better call for a batch: adding `m` ranges one at a time is `O(mn)`, whereas concatenating all of them and merging once is `O((n + m) log(n + m))`.
  • Can a binary search make the insert logarithmic?
    The search for the first interval that reaches the new range is `O(log n)` because the list is sorted, but that is only the locating step. In a flat array the elements after the insertion point must shift or be copied, which is linear, so the operation stays `O(n)`. A structure that splices cheaply in the middle can realise the benefit; claiming `O(log n)` for an array-backed list is the common overstatement.
  • What does the output look like if the new range sits entirely inside an existing one?
    Phase two absorbs that single stored interval, and because the widening takes the minimum start and maximum end, the widened range comes out identical to the stored one. The output is content-identical to the input, produced without any containment branch. That case is worth a fixture precisely because it exercises the min and the max simultaneously without changing anything.

saying these in an interview costs you the question

  • Appends then re-sorts, ignoring the existing order
  • Claims an array-backed insert is O(log n)
  • Compares against the original end, not the widened one
  • Adds special branches for empty or trailing inserts
  • Assumes only one stored interval can be absorbed

context

resolving links…