Dynamic Programming, Scheduling, And Set Cover

What's being tested

These problems test dynamic programming for combinatorial optimization, especially when brute force over subsets or schedules is too large. Expect to recognize weighted interval scheduling, knapsack/subset-cover search, and memoized multidimensional state while explaining correctness, tie-breaking, and complexity.

Patterns & templates

• Weighted interval scheduling — sort jobs by end time; use bisect_right to find previous compatible job; recurrence dp[i] = max(dp[i-1], profit[i] + dp[p(i)]).

• Inclusive/exclusive interval handling — clarify whether a job ending at t can precede one starting at t; this changes bisect_right vs bisect_left.

• Set cover via bitmask DP — map required services to bits; update dp[mask | providerMask] = minCost; works well when services $\leq$ 20–25.

• Backtracking with pruning — enumerate combinations for small n; sort by cost, prune when current cost exceeds best, and use deterministic tie-breaking.

• Knapsack-style capacity DP — for capacity-constrained property selection, track reachable sums/counts; reconstruct minimal set and handle exact vs at-least constraints.

• Memoization on multidimensional state — use @lru_cache over (idx, remainingA, remainingB, remainingC) or normalized tuples; prune dominated states aggressively.

• Cost/profit overflow awareness — use 64-bit integers conceptually; Python is safe, but mention long long/int64 in typed languages.

Common pitfalls

Pitfall: Treating interval scheduling as greedy by highest reward or shortest duration; weighted scheduling needs DP because local choices can block better combinations.

Pitfall: Forgetting deterministic tie-breaking when multiple minimal covers or property sets exist; define order before coding.

Pitfall: Using exponential subset enumeration when the intended constraint supports bitmask DP, binary search, or memoization.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.