Module F-10·10 min read

Merging overlapping intervals, meeting-room scheduling, and sweeping sorted events in one pass.

Written by Jatin Jain Saraf · Architect of SupraScan

Module F-10 — Intervals and Line Sweep

What this module covers: So far, this course has dealt with single points or contiguous runs within one sequence. This module shifts to reasoning about many ranges at once — meetings on a calendar, time periods, numeric bands — and the two techniques that make sense of them efficiently: sorting-and-merging, and sweeping through start/end events in order while tracking a running count.

Representing Intervals

An interval is just a pair — a start and an end:

type Interval = [number, number]; // [start, end]
 
const meetings: Interval[] = [[1, 3], [2, 6], [8, 10], [15, 18]];

The moment you have a collection of these, two questions come up constantly: which ones overlap and should be merged into one? and how many are active at the same time, at peak? Both questions have the same starting move: sort first, so overlaps and boundaries become adjacent and easy to detect in a single pass.

Merging Overlapping Intervals

Sort by start time, then walk through once: if the current interval's start is within the previous interval's range, merge them by extending the end; otherwise, start a new interval.

function mergeIntervals(intervals: Interval[]): Interval[] {
  if (intervals.length === 0) return [];
 
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]); // sort by start (Modules P-9/P-10)
  const merged: Interval[] = [sorted[0]];
 
  for (let i = 1; i < sorted.length; i++) {
    const current = sorted[i];
    const last = merged[merged.length - 1];
 
    if (current[0] <= last[1]) {
      // Overlaps (or touches) the last merged interval — extend it instead of adding a new one
      last[1] = Math.max(last[1], current[1]);
    } else {
      merged.push(current);
    }
  }
 
  return merged;
}
 
mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]]);
// [[1, 6], [8, 10], [15, 18]] — [1,3] and [2,6] overlap and merge; the others stand alone

Sorting costs O(n log n) (Modules P-9/P-10), and the merge pass afterward is a single O(n) walk — no interval is ever compared against more than its immediate predecessor, because sorting has already guaranteed that any interval it could overlap with is sitting right next to it. Without sorting first, you'd be back to comparing every interval against every other one — O(n²).

Line Sweep: Counting Overlaps at Any Moment

A different question: what is the maximum number of intervals active at the same time? — the classic "minimum meeting rooms needed" problem. The insight is to stop thinking about intervals as units and instead think about the individual start and end events, sorted in time order, sweeping through them like a line moving left to right across a timeline.

function minMeetingRooms(intervals: Interval[]): number {
  const starts = intervals.map(([s]) => s).sort((a, b) => a - b);
  const ends = intervals.map(([, e]) => e).sort((a, b) => a - b);
 
  let rooms = 0;
  let maxRooms = 0;
  let s = 0, e = 0;
 
  while (s < starts.length) {
    if (starts[s] < ends[e]) {
      rooms++;       // a meeting starts before the earliest ongoing one ends — needs another room
      s++;
    } else {
      rooms--;       // a meeting ends before (or as) the next one starts — free up its room
      e++;
    }
    maxRooms = Math.max(maxRooms, rooms);
  }
 
  return maxRooms;
}
 
minMeetingRooms([[0, 30], [5, 10], [15, 20]]); // 2

Separating starts and ends into two sorted arrays and sweeping through both with two pointers (Module F-8) turns "how many meetings overlap at the busiest moment" into a single pass: every start event increments a running count, every end event decrements it, and the peak value the counter ever reaches is the answer. This is the line sweep technique — process discrete events in time order, maintaining a running total, rather than checking every pair of intervals for overlap directly (which would be O(n²)).

function insertInterval(intervals: Interval[], newInterval: Interval): Interval[] {
  const result: Interval[] = [];
  let i = 0;
 
  // 1. Every interval entirely before the new one — keep as-is
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }
 
  // 2. Every interval overlapping the new one — merge them all together
  let merged = newInterval;
  while (i < intervals.length && intervals[i][0] <= merged[1]) {
    merged = [Math.min(merged[0], intervals[i][0]), Math.max(merged[1], intervals[i][1])];
    i++;
  }
  result.push(merged);
 
  // 3. Every interval entirely after — keep as-is
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }
 
  return result;
}