Why does greedily picking the highest-value non-adjacent ad slots miss the optimal schedule?
answer
- ask what a pick costs, not pays
- one choice blocks both neighbours
- two good neighbours can beat one great
- compare a skip-branch against a take-branch
- the take-branch reaches back two slots
basics
~20 sGreedy commits to a big slot before knowing what it blocks: taking a slot forbids both neighbours, so two merely good neighbours can outvalue one great slot. The take-or-skip recurrence best(i) = max(best(i-1), value(i) + best(i-2)) weighs both futures.
solid answer
~40 sGreedy fails because a slot's value does not tell you what the pick *costs*. Taking a slot forbids both of its neighbours, so one 60-thousand slot can knock out two 50s that are worth 100 together. The fix is a take-or-skip recurrence swept left to right: `best(i) = max(best(i-1), value(i) + best(i-2))` — either skip slot `i` and inherit the best schedule through `i-1`, or take it, collect `value(i)`, and jump back to `i-2` because `i-1` is now blocked by the shared setup crew. Seed it with `best(0) = value(0)` and `best(1) = max(value(0), value(1))`. Each slot is visited once, so it is O(n) time, and because only the previous two answers are ever read you can carry two rolling variables instead of a whole table — O(1) extra space.
go deeper
Be ready to state the recurrence out loud and show one small sequence where taking the biggest value first loses. Knowing that each slot has exactly two options, take or skip, is most of the answer.
Explain why the take-branch reaches back two positions rather than one, name the base cases, and show that only two previous answers are ever read, so the table compresses to constant space.
Expect to be pushed on reconstruction and on variants: wrap-around conflicts, wider conflict windows, or per-slot costs. Show that the state definition survives and only the reach of the take-branch changes.
Own the framing: this is the smallest example of replacing a defensible-sounding heuristic with an exact linear algorithm. Be able to say when a greedy approximation is still the right call because the exact version costs more to maintain than the revenue it recovers.
## The scenario A broadcast day is a row of premium ad slots, `value(0) ... value(n-1)`, each with a revenue figure. Two slots that sit next to each other need the same setup crew, so you may never sell two adjacent slots. Choose a set of non-adjacent slots that maximizes total revenue. This is the canonical *take-or-skip* one-dimensional dynamic program, and its whole teaching value is that the obvious greedy strategies are wrong for a reason you can state precisely. ## Why the greedy strategies fail Two greedy rules occur to almost everyone. **Alternate.** Take slots 0, 2, 4, ... (or 1, 3, 5, ...) and pick whichever total is larger. This is optimal only by accident: it ignores values entirely, and any sequence where the good slots are not evenly spaced defeats it. **Biggest first.** Repeatedly take the highest remaining value and delete its neighbours. This one is more seductive because it does look at values — but it evaluates a slot by what it *pays* while the constraint is about what it *costs*. Consider the values `10, 50, 60, 50, 10`. Biggest-first takes 60, which deletes both 50s, then mops up the two 10s for a total of **80**. The optimum takes the two 50s, which are not adjacent to each other, for **100**. The 60 was never worth its blast radius. The general lesson: a locally optimal pick can only be defended if you know the value of the best schedule for everything it does *not* block, and that value is exactly what the dynamic program computes. ## The state and the recurrence Define one number per prefix: > `best(i)` = the maximum revenue obtainable from slots `0 .. i`, obeying the no-adjacent rule. Note the shape of the definition: it is *the best answer for a prefix*, not *the best answer that uses slot i*. Both definitions can be made to work, but this one gives the cleaner transition, because at slot `i` there are exactly two mutually exclusive possibilities: - **Skip `i`.** Then the answer is whatever was best through `i-1`: `best(i-1)`. - **Take `i`.** Then slot `i-1` is unusable, so you may add `value(i)` to the best answer through `i-2`: `value(i) + best(i-2)`. Nothing else is possible, and the two branches do not interact, so: `best(i) = max(best(i-1), value(i) + best(i-2))` Base cases: `best(0) = value(0)`, and `best(1) = max(value(0), value(1))`. If you prefer to avoid special cases, define `best(-1) = 0` and `best(-2) = 0` and run the loop from `i = 0`. Trace it on `10, 50, 60, 50, 10`: | i | value | skip = best(i-1) | take = value + best(i-2) | best(i) | |---|-------|------------------|--------------------------|---------| | 0 | 10 | 0 | 10 | 10 | | 1 | 50 | 10 | 50 | 50 | | 2 | 60 | 50 | 70 | 70 | | 3 | 50 | 70 | 100 | 100 | | 4 | 10 | 100 | 80 | 100 | The answer is 100, and the table shows the moment greedy went wrong: at `i = 3` the take-branch reaches back over the 60 to the 50 at index 1. ## Why the recurrence is legitimate Two properties justify it. **Optimal substructure**: an optimal schedule over `0..i` restricted to `0..i-1` or `0..i-2` is itself optimal there, because the no-adjacent constraint is local — removing the last slot cannot make an earlier arrangement illegal. **Overlapping subproblems**: a naive recursive version calls `best(i-1)` and `best(i-2)`, which both call `best(i-3)`, giving exponential branching; storing each prefix answer once collapses that to n evaluations. ## Cost Time is O(n): one constant-work step per slot. Space is O(n) if you keep the table, but the transition only ever reads the two previous entries, so two rolling variables — call them `prev` and `prevPrev` — reduce it to O(1). Keep the table only when you must reconstruct *which* slots were sold: walk back from `i = n-1` and, at each step, if `best(i) == best(i-1)` the slot was skipped, otherwise it was taken and you jump to `i-2`. ## Variants worth recognizing If the schedule wraps — the last slot of the day shares a crew with the first — the two ends conflict and a single sweep is no longer valid. The standard repair is to run the same linear recurrence twice, once over slots `0 .. n-2` and once over `1 .. n-1`, and take the larger, because the optimum cannot include both ends. If the conflict window is wider than one neighbour (a crew needs two slots to reset), the take-branch reaches back further: `value(i) + best(i-3)`. The state definition never changes; only how far the take-branch jumps.
- How would you recover which slots were sold, not just the revenue?Keep the full table instead of two rolling variables, then walk backwards from the last index. At each step compare best(i) with best(i-1): if they are equal the slot was skipped, so move to i-1; otherwise the slot was taken, record it, and jump to i-2. That reconstruction is O(n) time and needs the O(n) table, which is the only reason to give up the constant-space version.
- What changes if the broadcast day wraps, so the last slot conflicts with the first?A single left-to-right sweep can no longer see the wrap-around conflict. Since an optimal schedule cannot contain both ends, run the same linear recurrence twice — once excluding the last slot, once excluding the first — and take the larger result. Cost stays O(n) time and O(1) space; only the number of passes changes.
- Why can you drop the table down to two variables here?The transition reads only best(i-1) and best(i-2), never anything older, so the table is a sliding window of width two. Carry prev and prevPrev, update them in place each iteration, and space falls from O(n) to O(1). The moment you need to reconstruct the chosen slots, that compression has to be given up.
Picking the loudest bidder in a room where winning also silences the two people beside you: the loudest voice can cost you two quieter ones that together say more.
saying these in an interview costs you the question
- Claims picking the largest value first is always optimal
- Takes every other slot regardless of the values
- Writes the take-branch as value(i) + best(i-1), allowing adjacency
- Defines the state as best answer that ends at i, then forgets to take a maximum
- Says the problem needs backtracking over all subsets