Activity Selection & Jump Game
DSA · Intermediate
Definition
Greedy choices like 'earliest finishing activity' or 'farthest reachable index' give optimal answers.
Classic proofs-of-greedy interview problems.
Diagram
Flowchart
Example: Jump game
nums = [2, 3, 1, 1, 4]
reach = 0
for i, x in enumerate(nums):
if i > reach: break
reach = max(reach, i + x)
print(reach >= len(nums) - 1)Output: True
Complexity
O(n log n) with sorting
Key points
- Prove greedy with an exchange argument
- If unsure, DP is safer
Interview questions
Why earliest finish?
It leaves the most time for the remaining activities.