Intervals

The one setup step that unlocks almost everything

Intervals arrive in whatever order the input gives them — which tells you nothing useful. Sort them by start time first, and suddenly you only ever need to compare each interval against the most recent one you've processed, instead of checking against all of them. That single sort is the setup step for nearly every interval problem you'll see.

Merging overlapping intervals

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]); // sort by START — enables the single left-to-right pass

  const result = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    const [start, end] = intervals[i];
    const last = result[result.length - 1];

    if (start <= last[1]) {
      last[1] = Math.max(last[1], end); // overlaps — extend the last merged interval
    } else {
      result.push([start, end]); // no overlap — starts a new group
    }
  }
  return result;
}

Inserting a new interval into an already-sorted, non-overlapping list

function insert(intervals, newInterval) {
  const result = [];
  let i = 0;

  // 1. everything that ends before newInterval starts — keep as-is
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i++]);
  }

  // 2. everything that overlaps newInterval — merge it in
  while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
    newInterval = [
      Math.min(newInterval[0], intervals[i][0]),
      Math.max(newInterval[1], intervals[i][1]),
    ];
    i++;
  }
  result.push(newInterval);

  // 3. everything that starts after newInterval ends — keep as-is
  while (i < intervals.length) result.push(intervals[i++]);

  return result;
}

Three clean phases instead of one tangled loop — this is a genuinely common interview shape: split the problem into "before," "during," and "after" relative to the thing you're inserting.

Minimum number of rooms/resources needed (meeting rooms)

How many overlapping meetings exist at the same time, at once? Track starts and ends as separate sorted event streams — whenever a meeting starts before the earliest still-running meeting ends, you need another room.

function minMeetingRooms(intervals) {
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b);
  const ends = intervals.map(i => i[1]).sort((a, b) => a - b);

  let rooms = 0, maxRooms = 0;
  let s = 0, e = 0;
  while (s < starts.length) {
    if (starts[s] < ends[e]) {
      rooms++;       // a meeting started before the earliest one ended
      s++;
    } else {
      rooms--;       // a meeting ended — free up a room
      e++;
    }
    maxRooms = Math.max(maxRooms, rooms);
  }
  return maxRooms;
}

This is the same idea as the sliding-window pattern from the beginner tier, applied to time instead of an array — "how many things are active at once" is a two-pointer sweep over sorted event boundaries.

A min-heap solves the same problem too: push each meeting's end time when it starts, and if the heap's minimum end time is ≤ the new meeting's start, pop it (reuse that room) instead of allocating a new one — heap size at the end is the room count. Both approaches are O(n log n); the two-pointer version above just avoids the heap's constant-factor overhead.

Recognizing it in an unseen problem

• Input is a list of [start, end] pairs, or "meetings," "bookings," "ranges"
• "Merge," "overlap," "how many at the same time," "minimum rooms/resources"
• Almost always starts with sorting by start (or end, for the greedy scheduling case in the previous chapter) — decide which based on what the question actually asks
• If it also involves inserting one new interval into an existing sorted set, think in three phases: before, overlapping, after