p83 — Task Scheduler

Source: LeetCode 621 · Medium · Topics: Greedy, Heap, Counting, Math Companies (2024–2025): Amazon (high), Meta (high), Google (medium) Loop position: Two equivalent solutions; choose your weapon. Heap simulation vs closed-form derivation. Tests whether you can recognize when algebra trumps simulation.

1. Quick Context

Tasks A, B, … need 1 unit time. Same-letter tasks must be separated by ≥ n idle units. Return minimum total time (including idles) to finish all.

Closed form: Let f_max = max frequency, c = count of tasks with that max frequency.

answer = max(len(tasks), (f_max - 1) * (n + 1) + c)

Heap simulation: Always run the highest-remaining-count task that isn’t on cooldown.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/task-scheduler/

STOP. 30-min timer. Solve with heap first, then derive the closed form.

3. Prerequisite Concepts

  • Max-heap (Python: negate counts).
  • Counter from collections.
  • Pigeonhole reasoning over frame slots.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Schedule single-unit tasks with same-letter cooldown of n; minimize total time.

2. Clarify: Cooldown counts idle slots; case sensitive; n can be 0.

3. Examples: tasks=AAABBB, n=2 → A B _ A B _ A B = 8. tasks=A, n=100 → 1.

5. Brute: Backtracking over orderings; exponential.

6. Target: O(N) closed-form or O(N log K) heap (K = distinct task types ≤ 26).

7. Pattern: Frame the most-frequent task as anchor; fit others into gaps.

8. Develop: see solution.py.

9. Test: n=0 (no cooldown → just len); all same letter; tie at max freq.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 The frame model

Place A’s first: A _ _ A _ _ A (f_max - 1 frames of size n+1, then a trailing A). Total slot count from this skeleton = (f_max - 1) * (n + 1) + 1. Now fit other tasks into the _ gaps. If they all fit, total = (f_max - 1) * (n + 1) + 1. If multiple tasks tie at f_max, append them to the end: +c where c = ties.

If the skeleton + fills uses fewer slots than there are tasks (when n is small and many distinct tasks), the answer is just len(tasks).

6.2 The closed-form derivation

answer = max(len(tasks), (f_max - 1) * (n + 1) + c)
  • (f_max - 1) * (n + 1) = slots in the first f_max - 1 frames.
  • + c = the last frame contains all max-frequency tasks (no idle needed for them, but they take c slots).
  • max(len(tasks), ...) handles the case where many task types fill all idle slots.

6.3 Heap simulation (equivalent answer)

Each cycle of n+1 time units: pop the n+1 highest-count tasks, run them; push back with count - 1 if still positive. If fewer than n+1 tasks available, fill remainder with idles (but only if heap is non-empty after pops, i.e., still tasks remaining). Time per cycle = n+1 (or until heap empty).

6.4 Why both give the same answer

The heap simulation is the execution of the frame model; the closed form is its algebraic summary. The heap is more intuitive; the closed form is O(K log K) (sort once) and trivially extends to “which letter goes in which slot”.

6.5 Family: gap/cooldown scheduling

  • LC 621 Task Scheduler (this).
  • LC 1834 Single-Threaded CPU (heap of (process_time, idx)).
  • LC 1882 Process Tasks Using Servers (two heaps).
  • LC 358 Rearrange String k Distance Apart (same problem, return arrangement not length).

6.6 Variant — return the actual schedule

Heap simulation gives the schedule for free. Closed form needs a reconstruction pass: place max-freq tasks first at distances n+1, then round-robin remaining tasks into the gaps.

7. Anti-Pattern Analysis

  1. Brute backtracking — N! permutations; never finishes.
  2. Sort tasks by count and lay them out greedily without the frame model — incorrect when ties at f_max.
  3. Forget max(len(tasks), ...) — closed form under-counts when many distinct tasks fill all idles.
  4. Use c = 1 always — wrong if multiple tasks tie at f_max.
  5. Off-by-one on (f_max - 1) * (n + 1) — using f_max * n + 1 or similar.
  6. Heap pops one at a time and decrements n separately — fragile; cleaner to pop a batch of n+1 per cycle.

8. Skills & Takeaways

  • Closed-form derivation from a “frame + fill” model.
  • Max-heap with cooldown via a temporary buffer.
  • Choosing algebra over simulation when structure permits.

9. When to Move On

  • Derive the closed form unprompted in 5 min after the heap solution.
  • Articulate the +c term.
  • Cite LC 358 (Rearrange String k Distance Apart) as the “return the schedule” variant.

10. Company Context

  • Amazon: L5/L6; appears in scheduling-flavored rounds.
  • Meta: E5; loves the closed-form derivation.
  • Google: L5; checks understanding of c.

Strong: “Two solutions: O(N log K) heap simulation and O(N + K) closed-form max(N, (f_max-1)(n+1) + c); derived from frame model; cited rearrange-string sibling.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
Heap simBuggy cooldownWorksClean+ extracts schedule
Closed formNoneAfter hintDerives+ proves equivalence to heap
+c termMissesAfter testCold+ handles edge n=0 cleanly
FamilyNoneNoneRearrange String+ multi-resource scheduling LP

12. Level Delta

  • Mid (L4): Heap simulation buggy; needs guidance on cooldown.
  • Senior (L5): Both heap and closed-form, with derivation; correct c and max(N, ...).
  • Staff (L6): + extracts actual schedule; + cites LP relaxation of multi-resource version.
  • Principal (L7+): + reduces to graph coloring (interval graph) for the multi-machine generalization; + cites EDF (Earliest Deadline First) and rate-monotonic scheduling from RTOS literature.

13. Follow-up Q&A

Q1: Multiple machines (m parallel workers)? A1: Closed form: max(ceil(N/m), ceil(f_max * (n+1) / m)) — but exact answer is NP-hard for arbitrary task graphs; LP relaxation works.

Q2: Tasks have priorities (some letters cheaper)? A2: Heap by (priority, count); closed form breaks.

Q3: Return the actual sequence (not length)? A3: Heap pops naturally produce it; or place anchors then round-robin fill.

Q4: Cooldown varies per pair (A-B has cooldown 2, A-C has 5)? A4: General graph coloring; NP-hard.

Q5: Streaming — tasks arrive online? A5: Online scheduling; competitive ratio analysis (e.g., 2-competitive for SRPT).

14. Solution Walkthrough

See solution.py:

  • least_interval_closed — O(N + K) closed form.
  • least_interval_heap — O(N log K) max-heap simulation.
  • least_interval_brute — backtracking oracle.

15. Beyond the Problem

Principal code review: “Task Scheduler illustrates the gap between simulation and algebraic summary. The heap version is correct, runs in O(N log K), and resembles what a junior would write. The closed form is O(N + K), reveals the actual structure (one anchor frame, ties at top, slack absorbed by other tasks), and generalizes immediately: change n to a per-pair cooldown and the closed form breaks but the model still informs your design. The Staff+ lesson: when you write a simulation, always ask ‘is there a closed form?’ — sometimes the answer is no (NP-hard), sometimes it’s a clever counting argument (this problem), sometimes it’s a known result (Birkhoff polytope decomposition for doubly stochastic matrices). Engineers who reach for simulation reflexively without first looking for structure ship O(n) code where O(1) would do — and worse, they ship code without understanding why it’s correct.”