Interview OS
Back to Coding Prep

Coding

Intervals

Sort by start, then merge/sweep overlapping ranges.

Coding pattern

Overview

Interval problems deal with ranges that may overlap — meetings, bookings, segments. Sorting by start (or end) then sweeping through lets you merge, count, or schedule in one linear pass after the sort.

How it works

Coding pattern
InputSortSweepOutputInterval list[s,e]By startsort by sMerge/overlapoverlap?Result
ClientServiceEdgeData

Step by step, with examples

  1. 1

    Interval list

    • Ranges each with a start and end.
  2. 2

    By start

    • Sort the intervals by start.
  3. 3

    Merge/overlap

    • Compare current end to the next start.
  4. 4

    Result

    • Return merged, free, or overlapping counts.
    • Example: Merge intervals, meeting rooms

When to reach for it

  • Merge intervals
  • Meeting rooms
  • Calendar conflicts

Example problem

Merge Intervals.

Approach

  • Sort by start
  • Extend the current interval while it overlaps, else push a new one

Solution

function merge(intervals) {
  intervals.sort((a,b) => a[0] - b[0]);
  const out = [intervals[0]];
  for (const [s,e] of intervals.slice(1)) {
    const last = out[out.length-1];
    if (s <= last[1]) last[1] = Math.max(last[1], e);
    else out.push([s,e]);
  }
  return out;
}

Complexity

Time O(n log n), Space O(n).

Common pitfalls

  • Not sorting first
  • Touching vs overlapping (<= vs <)

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions