Greedy algorithms and when they work in JavaScript

Problem

The meeting room

The coworking space has one meeting room. Eight requests have come in for tomorrow, each with a start and an end hour. Two meetings that overlap cannot be in the room at the same time. You want to accept as many teams as possible: every team you turn down goes to the competition.

The first ideas are simple rules: the earliest request first, or the shortest first (shorter ones take less time). You sort by the rule and accept every request that does not overlap the ones already accepted:

function book(requests, rule) {
  const taken = [];
  for (const [start, end] of [...requests].sort(rule)) {
    if (taken.every(([s, e]) => end <= s || e <= start)) {
      taken.push([start, end]);
    }
  }
  return taken;
}

function show(rule, taken) {
  const slots = taken.map(([s, e]) => `${s}–${e}`).join(", ");
  console.log(`${rule}: ${slots} (${taken.length})`);
}

show("By start", book(requests, (a, b) => a[0] - b[0]));
show("By length", book(requests, (a, b) => (a[1] - a[0]) - (b[1] - b[0])));
show("By end", book(requests, (a, b) => a[1] - b[1]));

By start: 8–16, 17–20 (2)
By length: 11–13, 14–16, 18–20 (3)
By end: 9–12, 12–15, 15–18, 18–20 (4)

By start gives 2 meetings, by length 3, and by end 4. Is 4 the most? Try all 2⁸ = 256 subsets: yes, 5 do not fit. But why exactly the rule "by end", and how can you be sure without trying everything?

The idea

A greedy algorithm

A greedy algorithm makes the choice that looks best now and never comes back to reconsider it. There is no table as in dynamic programming and no trying of every possibility: usually one sort and one pass.

For the room, greedy is: sort the requests by end and accept every one that starts no earlier than the moment the room becomes free. One variable, freeFrom, keeps that moment, so you do not have to compare with every meeting already accepted.

The three rules from the problem are all greedy. The difference is what they count as "best now", and only one of them is right. Greedy is fast and simple, but it comes without a guarantee: every greedy rule needs an argument that the choice at the moment does not spoil the future.

See it

Greedy by end

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if (start >= freeFrom) {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  return taken;
}

[...requests].sort(...) sorts a copy, and const [start, end] unpacks each pair.

const requests = [
  [8, 16], [12, 15], [9, 12], [15, 18],
  [11, 13], [17, 20], [14, 16], [18, 20],
];
const taken = maxMeetings(requests);
for (const [start, end] of taken) console.log(`${start}–${end}`);
console.log(`Meetings: ${taken.length}`);

9–12
12–15
15–18
18–20
Meetings: 4

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if (start >= freeFrom) {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  return taken;
}

Step by step, in words

Eight requests for one meeting room, in the order they came in. Sort them by end: first is the one that ends earliest.
The orange line is where the room becomes free. At the start nothing is booked: free from 0.
Request 1 (9–12) starts at 9, the room is free from 0: take it. Now the room is busy until 12.
Request 2 (11–13) starts at 11, before 12: it overlaps a meeting already taken, decline it.
Request 3 (12–15) starts at 12, the room is free from 12: take it. Now the room is busy until 15.
Request 4 (8–16) starts at 8, before 15: it overlaps a meeting already taken, decline it.
Request 5 (14–16) starts at 14, before 15: it overlaps a meeting already taken, decline it.
Request 6 (15–18) starts at 15, the room is free from 15: take it. Now the room is busy until 18.
Request 7 (17–20) starts at 17, before 18: it overlaps a meeting already taken, decline it.
Request 8 (18–20) starts at 18, the room is free from 18: take it. Now the room is busy until 20.
4 meetings: 9–12, 12–15, 15–18, 18–20. Each one taken ends the earliest of the rest, so it leaves the most of the day for the others.

Every meeting accepted leaves the room free as early as possible. The declined ones are no loss: each of them overlaps a meeting that ends no later than it does.

More precisely, if you are curious

If two requests end at the same hour, the order between them does not change the count: once the first one is accepted, the second one starts before its end. The built-in sort is stable in all four languages (equal items stay in the order they came in), so the output is the same everywhere.

Array.prototype.sort has been stable since ES2019. Without a compare function it sorts as text: [9, 12].sort() gives [12, 9].

Try it

Find the bug

A colleague copied the greedy algorithm and got only three meetings:

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if (start > freeFrom) {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  return taken;
}

const requests = [
  [8, 16], [12, 15], [9, 12], [15, 18],
  [11, 13], [17, 20], [14, 16], [18, 20],
];
const taken = maxMeetings(requests);
for (const [start, end] of taken) console.log(`${start}–${end}`);
console.log(`Meetings: ${taken.length}`);

9–12
14–16
17–20
Meetings: 3

Which line is the bug on?

Pick the line with the bug.

The idea

Why by end is right: the exchange argument

Take any best schedule, for example one with 4 meetings. Sort its meetings by time. Greedy first takes the request that ends earliest of all, say 9–12.

The first meeting of the best schedule ends no earlier than 12, because 12 is the earliest end of all.
Swap it for 9–12. The other meetings of the schedule start after the end of the old first one, so after 12 too: nothing overlaps, and the count is the same.
Now both schedules start the same way. Remove 9–12 and the requests that overlap it, and repeat the same for the rest.

Step by step you turn the best schedule into the greedy one without losing a single meeting. So greedy is at least as good as the best: it is the best.

The same argument fails for the other two rules. By start, 8–16 comes first: put it in the place of the first meeting and it shuts the room until 16, and the other meetings no longer fit.

More precisely, if you are curious

Formally the argument is induction on the number of meetings accepted: after k steps there is a best schedule that starts with the first k greedy choices. This is the standard way to prove a greedy algorithm: "the greedy choice is safe" (there is a best solution that contains it) plus "optimal substructure" (the rest is the same task, only smaller). The second property is shared with dynamic programming. The first one is what is missing when greedy fails.

Try it

Fill in the condition

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if () {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  return taken;
}

The idea

A second example: change in euros

The shop's till gives change with as few coins as possible. The euro coins are €2, €1, 50, 20, 10, 5, 2 and 1 cent. Greedy: give the biggest coin that still fits in what is left.

const COINS = [200, 100, 50, 20, 10, 5, 2, 1];

function change(cents) {
  const given = [];
  for (const coin of COINS) {
    while (cents >= coin) {
      given.push(coin);
      cents -= coin;
    }
  }
  return given;
}

function pay(cents) {
  const given = change(cents);
  console.log(`${cents} cents: ${given.join(" ")} (${given.length} coins)`);
}

pay(485);

485 cents: 200 200 50 20 10 5 (6 coins)

For the euro coins this gives the fewest coins for every amount: it is checked against the change table for every amount up to €5. The coins were chosen that way on purpose.

The rule "biggest first" is not right for any coins, though. With coins of 1, 3 and 4 cents, for 6 cents greedy gives 4 + 1 + 1, three coins, and two are enough: 3 + 3. There is no sign you can see at a glance: even with coins each at least twice the next one, greedy can fail. With 1, 4 and 9 cents, for 12 cents it gives 9 + 1 + 1 + 1, and 4 + 4 + 4 is enough. How to look for such cases is in the next lesson.

Try it

Predict the output

const COINS = [200, 100, 50, 20, 10, 5, 2, 1];

function change(cents) {
  const given = [];
  for (const coin of COINS) {
    while (cents >= coin) {
      given.push(coin);
      cents -= coin;
    }
  }
  return given;
}

function pay(cents) {
  const given = change(cents);
  console.log(`${cents} cents: ${given.join(" ")} (${given.length} coins)`);
}

pay(99);

Answer

99 cents: 20 20 20 20 10 5 2 2 (8 coins)

99 cents: 50 20 20 5 2 1 1 (7 coins)

99 cents: 50 20 20 5 2 2 (6 coins)

The idea

A third example: Kruskal

An internet provider connects neighbourhoods with fibre cable. Every cable laid has a price, and the goal is for all neighbourhoods to be connected for as little money as possible. That is the minimum spanning tree, and Kruskal builds it greedily: it sorts the possible cables by price and takes each next cheapest one, unless it closes a loop (the two neighbourhoods are already connected). Who is connected to whom is kept by union-find.

Here too the argument is an exchange: if the best tree does not contain the cheapest cable between two groups, put it in and remove the more expensive cable from the loop that closes. The price does not go up.

More precisely, if you are curious

Other familiar algorithms are greedy too. Dijkstra always takes the closest vertex not yet processed and never reconsiders it, and that is right because paths have no negative lengths. Huffman coding (behind ZIP and JPEG) always merges the two rarest symbols. What they share is one thing: each has a proof that the choice at the moment is safe.

See it

What it costs

Greedy is a sort, O(n log n), and one pass, O(n). Trying every subset is O(2ⁿ): with 20 requests that is over a million subsets, with 60 it never finishes. Here Bench sorts with merge sort and counts its comparisons. The built-in sort in your language makes a slightly different number, but it grows the same way.

Every subset O(2ⁿ)
Greedy by end O(n log n)

Algorithm	n = 10	n = 20	n = 1,000	n = 100,000	n = 1,000,000
Every subset	1,024	1,048,576	≈ 10³⁰¹	≈ 10³⁰¹⁰²	≈ 10³⁰¹⁰²⁹
Greedy by end	33	85	9,691	1,636,658	≈ 19,639,896

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

function maxMeetings(requests) {
  const byEnd = [...requests].sort((a, b) => a[1] - b[1]);
  const taken = [];
  let freeFrom = 0;
  for (const [start, end] of byEnd) {
    if (start >= freeFrom) {
      taken.push([start, end]);
      freeFrom = end;
    }
  }
  return taken;
}

Exercise

The courier

Solve the task in your editor.

The courier. A courier delivers parcels in a business park. Every customer has said in which window they are at the address: 9–11, 10–12, 11–14, 13–15, 14–17, 16–18 and 17–19. On every pass the courier leaves the parcels of everyone who is at the address right then. How few passes are needed, and at what hours? Write the greedy algorithm and print:

Passes at: 11, 15, 18 (3)

Hint: sort the windows by end. The first pass is at the end of the window that ends earliest: later you lose that customer, and earlier you serve no more. Then skip all windows that already contain that hour.

More tasks

The argument. Write the exchange argument for the courier: why is the first pass at the end of the earliest window no worse than the first pass of the best solution?
A second room. If the coworking space has two rooms, does "by end" work if you give each request to the room that became free the latest, but in time?
Prices. If the requests pay different amounts and you want the most money, not the most meetings, greedy by end is no longer right. Find three requests where it is not, and solve the task with the dynamic programming recipe.

Test

Check yourself

1. What makes an algorithm "greedy"?It keeps a table with the answers to the smaller tasksIt tries every possibility and keeps the bestAt every step it takes the best choice at the moment and never reconsiders it

2. Why are the room requests sorted by end and not by start?Because sorting by start is not possibleThe meeting that ends earliest leaves the most of the day for the restBecause sorting by end gives shorter meetings

3. Do the requests 9–12 and 12–15 overlap?It depends on the languageYes: both contain 12:00No: the first one ends exactly when the second one starts, that is why the check is >=

4. What does the exchange argument show?The first meeting of any best schedule can be swapped for the greedy choice without the count going downThat every greedy algorithm is correctThat greedy is faster than every subset

5. Change in euro coins is greedy. When does the same rule go wrong?Only for amounts over €5With coins of 1, 3 and 4 cents: for 6 cents greedy gives 4 + 1 + 1, and the fewest is 3 + 3Never: the biggest coin first is always best

Greedy algorithms and when they work

Cookies