Job Sequencing
Hard · rating 1900 · Greedy, Sorting
Each job takes one time slot and earns its profit only if finished by its deadline; you run at most one job per slot starting at slot 1. The first line has n. Each of the next n lines has a job's deadline and profit. Print the maximum total profit.
Constraints: 1 ≤ n ≤ 104, 1 ≤ deadline ≤ n
Editorial
Approach
Greedy by profit: consider jobs from most to least valuable, and schedule each in the latest still-free slot at or before its deadline. Leaving earlier slots open keeps room for other jobs that have tighter deadlines.
Why latest-slot is right
A high-profit job should occupy a slot only if it must; pushing it as late as possible preserves the flexible early slots for jobs that can't wait.
for deadline, profit in sorted(jobs, key=-profit):
t = min(deadline, n)
while t >= 1 and slots[t]: t -= 1
if t >= 1: slots[t] = True; total += profitComplexity
Time: O(n²) worst case (near-linear with a DSU). Space: O(n).
Related problems
- Minimum Meeting Rooms — Hard
- Double-Booked? — Medium
- Fit the Most Tasks — Medium
- Matchmaking Gap — Medium
- Shopping on a Budget — Medium
- Minimum Patrol Guards — Hard