Intervals

Overview

Interval problems deal with ranges [start, end]: meetings, bookings, time slots, number ranges. Almost all of them start the same way: sort by start time (or end time), then scan once while comparing each interval with the previous one or with a running boundary.

Two intervals [a, b] and [c, d] overlap when a <= d and c <= b. Merging, inserting, counting rooms, and removing overlaps are all variations of this check combined with the right sort order and a greedy choice.

When to use it

• Input is a list of ranges, time slots, or segments.
• The problem mentions overlap, merge, conflict, free time, rooms, or arrows.
• You need the minimum number of resources to host all intervals.
• You need the maximum number of non-overlapping intervals.

Problem patterns it solves

Where it is used in real software

Key terms

Overlap

[a, b] and [c, d] overlap if a <= d and c <= b (use < for half-open intervals).

Merge

Replace overlapping intervals with [min start, max end].

Sort by start

Used for merging, inserting, and coverage.

Sort by end

Used for the greedy maximum set of non-overlapping intervals.

Sweep line

Process start and end events in order with a running count.

Merge intervals algorithm

1. 1
   Sort by start

   Overlapping intervals now sit next to each other.

2. 2
   Start the result with the first interval

   It is the current open block.

3. 3
   Compare each next interval with the last block

   If next.start <= last.end, they overlap.

4. 4
   Overlap: extend

   last.end = max(last.end, next.end). The max matters when one interval contains another.

5. 5
   No overlap: start a new block

   Push the interval to the result.

Merge [[1, 3], [2, 6], [8, 10], [15, 18], [9, 12]]

After sorting by start: [1, 3], [2, 6], [8, 10], [9, 12], [15, 18]

Three disjoint blocks. Sorting costs O(n log n) and the scan is O(n).

Implementation

1function merge(intervals) {2  intervals.sort((a, b) => a[0] - b[0]);3  const result = [intervals[0].slice()];4  for (let i = 1; i < intervals.length; i++) {5    const last = result.at(-1);6    const [start, end] = intervals[i];7    if (start <= last[1]) last[1] = Math.max(last[1], end);8    else result.push([start, end]);9  }10  return result;11}12 13// 435: minimum removals = n - maximum non-overlapping set (greedy by end)14function eraseOverlapIntervals(intervals) {15  intervals.sort((a, b) => a[1] - b[1]);16  let kept = 0, lastEnd = -Infinity;17  for (const [start, end] of intervals) {18    if (start >= lastEnd) {19      kept++;20      lastEnd = end; // the earliest finish leaves the most room21    }22  }23  return intervals.length - kept;24}25 26// 253: minimum meeting rooms with two sorted arrays27function minMeetingRooms(intervals) {28  const starts = intervals.map((i) => i[0]).sort((a, b) => a - b);29  const ends = intervals.map((i) => i[1]).sort((a, b) => a - b);30  let rooms = 0, best = 0, e = 0;31  for (let s = 0; s < starts.length; s++) {32    if (starts[s] < ends[e]) rooms++; // needs a new room33    else e++;                         // reuse a room that just freed up34    best = Math.max(best, rooms);35  }36  return best;37}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Forgetting max when merging.

  Fix: [1, 10] and [2, 3] merge to [1, 10], not [1, 3].

• Mutating the input intervals.

  Fix: Copy the first interval when building results if the caller needs the input.

• Comparator overflow in Java.

  Fix: Use Integer.compare(a[0], b[0]) rather than a[0] - b[0].

Interview questions

Practice problems