Greedy Algorithms Explained

Greedy is the simplest strategy there is: take the best thing available right now. It is also the easiest to get wrong, because a greedy solution that is subtly incorrect still returns a plausible answer.

The idea

At each step, make the choice that looks best in isolation. Never go back and reconsider. No cache, no table - usually just a sort and a single pass.

When it works it is faster and simpler than dynamic programming. The whole difficulty is knowing whether it works.

A case where it does

Interval scheduling: given meetings with start and end times, fit in as many as possible. Sort by end time and always take the next one that fits.

function maxMeetings(meetings) {
  // Earliest finishing first — that is the greedy choice.
  const sorted = [...meetings].sort((a, b) => a.end - b.end)

  let count = 0
  let lastEnd = -Infinity

  for (const meeting of sorted) {
    if (meeting.start >= lastEnd) {
      count++
      lastEnd = meeting.end
    }
  }

  return count
}

console.log(maxMeetings([
  { start: 1, end: 3 },
  { start: 2, end: 5 },
  { start: 4, end: 7 },
  { start: 6, end: 8 },
]))  // 3