Interval Scheduling

The interval scheduling maximization problem is solved optimally by a greedy algorithm that always picks the interval that finishes earliest, and a clean exchange argument proves why.

5 min read Level 2/5 #dsa#greedy#interval-scheduling

What you'll learn

Implement the earliest-finish-time greedy algorithm in O(n log n)
Sketch the exchange-argument proof that the greedy choice is optimal
Recognize variants such as interval partitioning and weighted interval scheduling

You have a single meeting room and a list of requested time slots. Each slot has a start and an end time. How many meetings can you schedule without any two overlapping? This is the interval scheduling maximization problem and it has a satisfying greedy solution.

The Greedy Rule

Sort the intervals by their end time and scan from left to right. Accept an interval if and only if it does not overlap with the last accepted one. That is it — no backtracking, no DP table.

function maxNonOverlapping(intervals) {
  // Sort by finish time ascending
  intervals.sort((a, b) => a.end - b.end);

  let count = 0;
  let lastEnd = -Infinity;

  for (const { start, end } of intervals) {
    if (start >= lastEnd) {   // no overlap with last accepted
      count++;
      lastEnd = end;
    }
  }

  return count;
}

// Example
const meetings = [
  { start: 1, end: 4 },
  { start: 3, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 3, end: 9 },
  { start: 6, end: 10 },
];

console.log(maxNonOverlapping(meetings)); // 3  ([1,4], [5,7], [6,10] — wait, [1,4],[5,7] then [6,10] overlaps; actual: [1,4],[5,7] = first two fit then [6,10] overlap; greedy picks [1,4],[5,7] that's 2 then checks [6,10] start=6>=7? no; result is [1,4],[3,5] no overlap check: 3<4 skip, [0,6] 0<4 skip, [5,7] 5>=4 accept lastEnd=7, [3,9] 3<7 skip, [6,10] 6<7 skip => 2 accepted after [1,4]; total=3 is wrong; let me recount)

function maxNonOverlapping(intervals) {
  intervals.sort((a, b) => a.end - b.end);
  // Sorted: [1,4],[3,5],[0,6],[5,7],[3,9],[6,10]
  // Accept [1,4] lastEnd=4 count=1
  // [3,5]: 3 < 4 skip
  // [0,6]: 0 < 4 skip
  // [5,7]: 5 >= 4 accept, lastEnd=7, count=2
  // [3,9]: 3 < 7 skip
  // [6,10]: 6 < 7 skip
  // Result: 2

  let count = 0;
  let lastEnd = -Infinity;
  for (const { start, end } of intervals) {
    if (start >= lastEnd) {
      count++;
      lastEnd = end;
    }
  }
  return count;
}

The dominant cost is the sort, so the overall complexity is O(n log n).

Why Earliest End Time Works

Exchange argument. Let G be the greedy solution and O be any other solution with more intervals. Let the first position where they differ be index k. G chose interval g and O chose interval o, where g ends no later than o (by construction). Swap o for g in O: the swap can only make room for more intervals later in the sequence because g ends earlier. Repeating this argument shows G has at least as many intervals as O, so G is optimal.

Choosing by earliest start time, shortest duration, or fewest conflicts each fails on a simple counterexample — earliest end time is the unique correct greedy key for this problem.

Collecting the Actual Intervals

function scheduleIntervals(intervals) {
  intervals.sort((a, b) => a.end - b.end);
  const selected = [];
  let lastEnd = -Infinity;
  for (const iv of intervals) {
    if (iv.start >= lastEnd) {
      selected.push(iv);
      lastEnd = iv.end;
    }
  }
  return selected;
}

Up Next

Apply greedy thinking to array reachability: the Jump Game problems.

Jump Games →