Greedy and Structure

What is this?

Both problems have short answers that are worthless without the argument behind them. Patch Array adds numbers so every sum up to n is reachable, and the rule — always add the smallest currently unreachable value — doubles the reachable range each time. Task Scheduler has a closed-form formula whose derivation is the interview; the code is one line.

💡 Fun fact: Task Scheduler needs no scheduling. Take the most frequent task, occurring mx times: it forces mx − 1 gaps of width n + 1, and then the tasks tied at that frequency finish the last block — giving (mx − 1) × (n + 1) + k. Every other task fits into the idle slots, and if there are too many to fit, they simply fill every idle slot and the answer becomes len(tasks). So the answer is max(len(tasks), (mx − 1) × (n + 1) + k). One line, no simulation, and the argument — that the busiest task alone determines the shape — is what is actually being asked for.

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

The one-line idea: find the quantity that constrains everything else — the smallest unreachable sum, the most frequent task — and the greedy follows from it, along with the proof you will be asked for.

1. The reachable range doubles

miss, i, patches = 1, 0, 0                       # everything in [1, miss) is reachable
while miss <= n:
    if i < len(nums) and nums[i] <= miss:
        miss += nums[i]; i += 1                  # extend using what we already have
    else:
        miss += miss; patches += 1               # patch with `miss` itself → range doubles
return patches

The invariant is the whole solution: every sum in [1, miss) is reachable. If the next available number is at most miss, adding it extends the range to miss + nums[i] with no gap. If it is larger, miss itself is unreachable and must be patched — and patching with exactly miss extends the range to 2 × miss, the largest extension any single number could give.

That doubling is also the complexity argument: the range at least doubles per patch, so at most O(log n) patches are ever needed.

2. The busiest task sets the length

c = Counter(tasks)
mx = max(c.values())                             # the most frequent task's count
k = sum(1 for v in c.values() if v == mx)        # how many tasks tie at that count
return max(len(tasks), (mx - 1) * (n + 1) + k)

The max against len(tasks) is the case people miss. When there are many distinct tasks, the idle slots fill up completely and no idling is required at all — the formula would then understate the answer, and the total task count is the true lower bound.

k matters because every task tied at the maximum frequency must appear in the final block, extending it by one each.

3. A 30-second worked example (patching)

nums = [1, 5, 10], n = 20

miss = 1    nums[0] = 1 ≤ 1     use it        miss = 2      [1,2) reachable
miss = 2    nums[1] = 5 > 2     PATCH with 2  miss = 4      [1,4)   patches = 1
miss = 4    nums[1] = 5 > 4     PATCH with 4  miss = 8      [1,8)   patches = 2
miss = 8    nums[1] = 5 ≤ 8     use it        miss = 13     [1,13)
miss = 13   nums[2] = 10 ≤ 13   use it        miss = 23     [1,23)
miss = 23 > 20 → done

patches: 2

Watch the two patches double the range each time — 2 to 4, then 4 to 8 — while the numbers already present extend it by their own value. After the second patch the array's own 5 and 10 are finally usable, and they carry the range past 20 on their own. Patching with anything smaller than miss would have left miss still unreachable; anything larger would have left a gap.

4. Where you'll actually meet this

• Denomination design. "Which coin or note values guarantee every amount is payable" is Patch Array.
• Test-case and coverage generation. Finding the smallest additions that make a range fully reachable.
• CPU and job scheduling with cooldowns. The Task Scheduler formula is the standard lower bound.
• Rate limiting and throttling. Minimum time to run a set of actions with a mandated gap between repeats.
• Capacity and denomination planning. Both problems appear in payments and inventory under different names.

5. Problems in this chapter

▶ Patch Array

Fewest additions so every sum in [1, n] is reachable. Track the smallest unreachable sum; use the next number when it fits, patch with miss otherwise.
Pattern: greedy with a doubling invariant. Target: O(len(nums) + log n) time, O(1) space.

▶ Task Scheduler

Least time to run all tasks with a cooldown between identical ones. Compute from the most frequent task's count and the number of tasks tied with it.
Pattern: closed-form from the binding constraint. Target: O(n) time, O(1) space.

6. Common pitfalls 🚫

• Patching with a number other than miss. Smaller leaves the gap; larger wastes the extension.
• Losing the invariant. State "everything in [1, miss) is reachable" out loud and every step follows.
• Overflow on miss += miss in fixed-width languages when n is near the integer limit.
• Forgetting max(len(tasks), …) in the scheduler, which understates the answer when idle slots fill.
• Omitting k, the number of tasks tied at the maximum frequency, which extends the final block.
• Simulating the scheduler. It works and it is O(n log n) for an O(n) problem — and the formula is what is being asked for.
• Stating a greedy without its argument. Both of these are judged on the proof.

7. Key takeaways

1. Find the binding constraint — the smallest unreachable sum, the busiest task — and the greedy follows.
2. An invariant makes a greedy provable. [1, miss) is the whole argument for Patch Array.
3. Doubling gives the complexity for free: at most O(log n) patches.
4. Patch with exactly the gap. It is the unique choice that neither wastes nor falls short.
5. A closed form can replace a simulation, and knowing why is the point.
6. Guard the formula with a lower bound. len(tasks) is not an edge case, it is a regime.
7. Why interviewers like it: both answers are three lines, so all the signal is in the explanation.

Order: Patch Array → Task Scheduler.