Interval and Scheduling Greedy

What is this?

Neither of these problems looks greedy when you first read it. One is about garden sprinklers, the other about the order dishes are cooked. In both cases the greedy is hidden behind the wording, and the work is the reframing — once a tap is drawn as an interval and a menu is sorted, the right move at each step becomes obvious.

That is worth naming as a skill in itself: many greedy problems are not "spot the greedy", they are "find the representation in which the greedy is visible".

💡 Fun fact: Reducing Dishes rewards a small piece of algebra. Cooking a dish at time t earns t × satisfaction, so adding one more dish at the front shifts every later dish one time slot later — increasing the total by exactly the sum of all dishes cooked from that point on. So sort ascending, walk from the most satisfying end, and keep adding while that running suffix total is still positive. The moment it turns negative, every further dish makes things worse, and you stop.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: change the representation until the greedy choice is obvious — a radius into an interval, a menu into a sorted sequence — then take the option with the furthest reach, or keep adding while the marginal gain stays positive.

1. Coverage as jumps

Convert each tap into the interval it waters, then record for every start position the furthest right it can reach:

reach = [0] * (n + 1)
for i, r in enumerate(ranges):
    if r == 0:
        continue
    left = max(0, i - r)
    reach[left] = max(reach[left], i + r)     # from `left`, we can get to `i + r`

Now it is the jump game. Sweep left to right maintaining the end of the current interval and the furthest reachable point; when you arrive at the current end, you must commit to a tap and the furthest reach becomes the new end:

taps, current_end, furthest = 0, 0, 0
for i in range(n):
    furthest = max(furthest, reach[i])
    if i == current_end:                       # must commit to a tap here
        if furthest <= i:
            return -1                          # cannot advance — a gap exists
        taps += 1
        current_end = furthest
    if current_end >= n:
        break
return taps

The greedy is safe by exchange: any optimal cover using a tap that reaches less far can be swapped for the further-reaching one without leaving a gap.

2. Sorted, then a suffix sum

For the dishes, sort ascending and walk from the largest downward, maintaining a running suffix sum:

satisfaction = [-1, -8, 0, 5, -9]  → sorted → [-9, -8, -1, 0, 5]

walk from the right:
   take 5      suffix = 5    total = 5          keep (suffix > 0)
   take 0      suffix = 5    total = 5 + 5 = 10 keep
   take -1     suffix = 4    total = 10 + 4 = 14 keep
   take -8     suffix = -4   → suffix is negative, STOP
                                            answer = 14

The running total is the answer because each step's gain is exactly the current suffix sum — the shift effect described above. Once the suffix goes negative, every further dish reduces the total.

3. Where you'll actually meet this

• Irrigation and coverage planning. Placing the fewest sprinklers, transmitters or sensors along a line.
• Media streaming and prefetching. Requesting the chunk that extends playable buffer furthest is the same jump greedy.
• Cell tower placement. Minimum stations covering a stretch of road, with each station's range as an interval.
• Menu and product-line design. Deciding how many items to keep when later items earn more but cost the earlier ones position.
• Task ordering with weighted completion times. The classic scheduling result that shorter-first minimises total weighted completion is the same suffix-sum reasoning.

4. Problems in this chapter

▶ Minimum Number of Taps to Open to Water a Garden

Fewest taps to cover [0, n]. Convert each tap to an interval, build a furthest-reach array, and run the jump-game sweep; return -1 when a gap cannot be crossed.
Pattern: interval reframing + furthest-reach greedy. Target: O(n) time, O(n) space.

▶ Reducing Dishes

Maximise the sum of time × satisfaction by choosing which dishes to cook. Sort ascending, accumulate from the top while the running suffix sum stays positive.
Pattern: sort + suffix-sum cut-off. Target: O(n log n) time, O(1) space.

5. Common pitfalls 🚫

• Forgetting radius zero. A tap with r = 0 waters nothing and must not create an interval.
• Not clamping the left edge. i - r can be negative; clamp to 0 or the array index is wrong.
• Missing the -1 case. If the furthest reach never passes the current end, a gap exists and the garden cannot be covered.
• Committing to a tap too early. You only choose when you arrive at the current interval's end, not on every index.
• Sorting descending for the dishes. Sort ascending and walk from the right; sorting the other way makes the suffix-sum argument awkward to state.
• Stopping at the first negative dish rather than the first negative suffix sum. A negative dish can still be worth including if the dishes above it outweigh it.
• Recomputing the total from scratch each step instead of accumulating — correct but O(n²).

6. Key takeaways

1. Reframe until the greedy is visible. A radius is an interval; fewest intervals is a jump game.
2. Furthest reach wins, and the exchange argument that proves it is one sentence.
3. Commit only at the boundary of the current interval, not at every position.
4. Sorting makes the marginal gain computable, and a suffix sum then tells you exactly where to stop.
5. The stopping rule is about the marginal gain, not about the individual item's sign.
6. Accumulate rather than recompute.
7. Why interviewers like it: the code is short and the reframing is the whole insight, so it is a clean test of whether you can change representation rather than attack the problem as stated.

Order: Minimum Number of Taps to Open to Water a Garden → Reducing Dishes.