Intervals: sort by start, then sweep

Sort the intervals by their start. After that, an interval can only overlap the block that came right before it. So one walk from left to right settles everything. On that walk you compare each interval only with the current block.

Think of it like this: laying calendar bookings out on a table in order of start time. You only ever compare the booking in your hand with the last block on the table. If they overlap, you stretch that block. If not, you start a new block next to it.

How to spot it

Words and constraints in a problem that point to this pattern:

• The input is a list of pairs such as [start, end]: meetings, bookings, time ranges
• “Overlap”, “conflict”, “clash”, “merge” or “combine”
• “Can one person attend all of them?” or “fewest to remove so none overlap”
• “Insert a new range” into a list of ranges
• Total time covered, or the free gaps between busy times

Watch it work

The template

type Interval = [number, number]; // [start, end]

// Do two intervals overlap? Each one must start before the other ends.
function overlaps(a: Interval, b: Interval): boolean {
  return a[0] < b[1] && b[0] < a[1]; // use <= if touching ends should count
}

// Sort by start, then walk once. onBlock is called with each merged block.
function sweep(intervals: Interval[], onBlock: (start: number, end: number) => void): void {
  if (intervals.length === 0) return;                         // nothing to sweep
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]);  // copy, then sort by start
  let [curStart, curEnd] = sorted[0];                         // the block being built
  for (let i = 1; i < sorted.length; i++) {
    const [start, end] = sorted[i];
    if (start < curEnd) {
      curEnd = Math.max(curEnd, end);    // overlap: stretch the block (it may already reach further)
    } else {
      onBlock(curStart, curEnd);         // gap: the current block is finished
      curStart = start;                  // and a new block starts here
      curEnd = end;
    }
  }
  onBlock(curStart, curEnd);             // the last block never meets a gap: close it here
}

// Example: total covered time
let total = 0;
sweep([[6, 8], [1, 3], [2, 5], [9, 10]], (s, e) => { total += e - s; }); // total = 7

Worked example

1. The first idea: go through the day hour by hour, or minute by minute. At each time, ask “is any meeting covering this time?” With 1,440 minutes and 1,000 meetings that's 1.4 million checks. Going hour by hour breaks as soon as a meeting starts at 9:30.

2. Notice what a gap really is. It's the space between two busy blocks, after you merge the overlapping meetings. [9, 11] and [10, 12] are one busy block [9, 12], and the gap after it starts at 12. So this is a sort-and-sweep problem.

3. Sort by start. Keep a variable freeFrom: everything before this time is already accounted for. It starts at dayStart. For each meeting, if it starts after freeFrom, the space between is a gap. Then push freeFrom forward to the meeting's end, using max so a short meeting inside a long one changes nothing.

   function freeSlots(busy: [number, number][], dayStart: number, dayEnd: number): [number, number][] {
     const sorted = [...busy].sort((a, b) => a[0] - b[0]);
     const gaps: [number, number][] = [];
     let freeFrom = dayStart;                             // everything before this is accounted for
     for (const [start, end] of sorted) {
       if (start > freeFrom) gaps.push([freeFrom, start]); // a hole before this meeting
       freeFrom = Math.max(freeFrom, end);                // the busy block reaches at least here
     }
     if (freeFrom < dayEnd) gaps.push([freeFrom, dayEnd]); // free time after the last meeting
     return gaps;
   }
   

4. Run it. Sorted: [9,11], [10,12], [13,15]. freeFrom starts at 8. 9 > 8, so add the gap [8, 9], and freeFrom becomes 11. 10 > 11? No. freeFrom becomes 12. 13 > 12, so add the gap [12, 13], and freeFrom becomes 15. After the loop, 15 < 18, so add the gap [15, 18]. Correct.

5. Edge cases: no meetings returns [[8, 18]]. Now add a meeting from 16 to 19. It gives the gap [15, 16] and pushes freeFrom to 19, so no final gap is added. A meeting from 7 to 9 starts before the day. 7 > 8 is false, so no fake gap appears.

Common mistakes

• Forgetting to sort first: with [[6, 8], [1, 3]] the sweep closes [6, 8] before it ever sees [1, 3], so blocks come out split or out of order.
• Calling .sort() with no compare function: JavaScript compares as strings, so [10, 12] sorts before [9, 11]. Always pass (a, b) => a[0] - b[0].
• Writing curEnd = end instead of Math.max(curEnd, end): with [1, 10] then [2, 3] the block shrinks to end at 3, and [5, 6] is wrongly treated as separate.
• Not closing the last block after the loop: the final merged interval is missing from the answer.
• Mixing < and <=: decide from the prompt whether [1, 3] and [3, 5] overlap, then use the same rule everywhere.

Cost

In interviews