Greedy choice

When to use it

Use it when you can say why the best-looking choice now can never spoil a better answer later, so nothing has to be kept open or tried again.

It belongs to the optimization group: Find the best answer without trying every possibility: reuse smaller answers, or take the safe choice first.

Watch it work

An exam hall has one row of desks. In desks, 1 is a desk where a pupil already sits and 0 is an empty desk. No two pupils may sit at neighboring desks. Return the largest number of new pupils that can be seated.

Input
desks = [0, 0, 1, 0, 0, 0, 0]

Output
3

The method

1. Copy the row and start with no new pupil seated
2. Decide each desk once, from left to right
3. A desk is allowed if it and both neighbors are empty
4. Take an allowed desk at once, and never undo it
5. Return how many pupils were seated

The run, one moment at a time

1. Step 1. The copy of the row starts like the hall: a 1 is a desk with a pupil, a 0 is an empty desk. No new pupil is seated yet.

   row: 0 0 1 0 0 0 0
   seated: 0
   

2. Step 2. Go along the row once. Each desk gets one decision, made from what is known at that moment, and that decision is never changed.

   row: 0 0 1 0 0 0 0
   seated: 0
   

3. Step 4. Desk 0 is empty and so is desk 1 beside it, so it is allowed. Seat a pupil here at once. Now 1 new pupil is seated.

   row: 1 0 1 0 0 0 0
   seated: 1
   

4. Step 3. Desk 1 is empty, but desk 0 beside it has a pupil. Not allowed: leave it empty.

   row: 1 0 1 0 0 0 0
   seated: 1
   

5. Step 3. Desk 2 already has a pupil, so it is not allowed. Move on.

   row: 1 0 1 0 0 0 0
   seated: 1
   

6. Step 3. Desk 3 is empty, but desk 2 beside it has a pupil. Not allowed: leave it empty.

   row: 1 0 1 0 0 0 0
   seated: 1
   

7. Step 4. Desk 4 is empty and so are desks 3 and 5, so it is allowed. Seat a pupil here at once. Waiting for desk 5 gains nothing: a pupil there would block desk 6 as well.

   row: 1 0 1 0 1 0 0
   seated: 2
   

8. Step 3. Desk 5 is empty, but desk 4 beside it has a pupil. Not allowed: leave it empty.

   row: 1 0 1 0 1 0 0
   seated: 2
   

9. Step 4. Desk 6 is empty and so is desk 5 beside it, so it is allowed. Seat a pupil here at once. Now 3 new pupils are seated.

   row: 1 0 1 0 1 0 1
   seated: 3
   

10. Step 5. 7 desks, 7 decisions, and none was taken back. In the end 3 new pupils are seated, and no other seating fits more.

    row: 1 0 1 0 1 0 1
    seated: 3
    

The code

The numbered comments are the steps of the method.

function solve(desks) {
  // 1. Copy the row and start with no new pupil seated
  const row = [...desks];
  let seated = 0;
  // 2. Decide each desk once, from left to right
  for (let i = 0; i < row.length; i++) {
    // 3. A desk is allowed if it and both neighbors are empty
    // A desk at an end of the row has no neighbor on that side.
    const left = i === 0 || row[i - 1] === 0;
    const right = i === row.length - 1 || row[i + 1] === 0;
    if (row[i] === 0 && left && right) {
      // 4. Take an allowed desk at once, and never undo it
      row[i] = 1;
      seated += 1;
    }
  }
  // 5. Return how many pupils were seated
  return seated;
}

def solve(desks):
    # 1. Copy the row and start with no new pupil seated
    row = list(desks)
    seated = 0
    # 2. Decide each desk once, from left to right
    for i in range(len(row)):
        # 3. A desk is allowed if it and both neighbors are empty
        # A desk at an end of the row has no neighbor on that side.
        left = i == 0 or row[i - 1] == 0
        right = i == len(row) - 1 or row[i + 1] == 0
        if row[i] == 0 and left and right:
            # 4. Take an allowed desk at once, and never undo it
            row[i] = 1
            seated += 1
    # 5. Return how many pupils were seated
    return seated

How to spot it

Asked: The largest number of items you can take, each counting as one

When every item counts the same, a choice is judged only by what it blocks. Often one choice blocks the least, and taking it first is safe.

Asked: Can the last position be reached, when shorter moves are always allowed?

Then reaching far also means reaching everything nearer. One number, the farthest point so far, stands for all the routes.

Asked: The largest sum of a run of neighbors, with negative numbers allowed

A run whose sum has dropped below zero only hurts what follows. Drop it and start again at the next number: one carried sum is enough.

Given: A running total that must never drop below zero

The moment it drops below zero, everything before that point is ruled out together. One pass settles each point as it is met.

Looks like it, but is not

• Pick items from a row, no two next to each other, and each item has its own value. Use One-dimensional dynamic programming. A small item taken early can block a large one beside it, so a choice can be regretted. Keep the best total for each beginning of the row.
• Pay an amount with the fewest coins, and the coin values can be anything. Use Knapsack dynamic programming. The largest coin first can be wrong. With coins 1, 3 and 4, the amount 6 is 3 + 3, not 4 + 1 + 1.
• Intervals are given, and you must merge the ones that overlap or count how many run at once. Use Sorted interval sweep. Nothing is chosen there. After sorting, each interval is only compared with what came before it, or counted.

Cost and mistakes

Time is one pass, about n steps, written O(n), because each desk is decided once from its two neighbors. Extra space is the copy of the row, n cells. A greedy method that must sort first pays for the sort too.

Watch out

• A rule that looks best is not yet proof. Try to break it: look for a small input where the best-looking first choice ends with a worse answer. If you find one, the choices must be kept in a table.
• Say in one sentence why the choice is safe, as here: the first allowed desk never blocks more than a later one. If you cannot say it, do not trust the rule.

In the 150

9 problems of the 150 use it. Naming them gives their method away, so the list is folded.