You are given a list of jobs, where each job is a pair [deadline, profit]. Every job takes exactly one unit of time, only one job can run at a time, and a job earns its profit only if it finishes on or before its deadline (time runs in unit slots 1, 2, 3, ...).
Return a two-element array [count, total_profit]: the maximum number of jobs you can complete on time and the maximum total profit achievable.
Input: jobs = [[2,100],[1,19],[2,27],[1,25],[1,15]] Output: [2, 127] Schedule [2,100] in slot 2 and [2,27] in slot 1 — 2 jobs, total profit 127.
Input: jobs = [[4,20],[1,10],[1,40],[1,30]] Output: [2, 60] Take [1,40] in slot 1 and [4,20] in slot 4 — 2 jobs, total profit 60.
- 1 <= jobs.length <= 10^5 - 1 <= deadline <= jobs.length - 1 <= profit <= 500
Every job takes the same one unit of time, so profit is all that separates them: you want the most profitable jobs to make the cut. Consider jobs in decreasing profit and give each the latest free slot on or before its deadline — placing it late keeps earlier slots open for jobs with tighter deadlines.
“How long does each job take?”
Exactly one unit of time, so a job with deadline d can occupy any one slot in 1..d.
“What am I maximizing?”
Total profit first; the count reported is how many jobs that best schedule includes.
“Which slot should a chosen job take?”
The latest free slot at or before its deadline, to leave early slots for tighter-deadline jobs.
Since every job is one time unit, I want the highest-profit jobs scheduled.
I'll sort by profit descending and place each job in the latest free slot up to its deadline.
Scheduling it as late as possible preserves earlier slots for jobs that can only run early.
Worked example — jobs = [[2, 100], [1, 19], [2, 27], [1, 25], [1, 15]]
sort by profit: [2,100] [2,27] [1,25] [1,19] [1,15] [2,100] -> slot 2 free -> take (profit 100) [2,27] -> slot 2 taken, slot 1 free -> take (profit 127) [1,25] -> slot 1 taken -> drop [1,19] -> slot 1 taken -> drop [1,15] -> slot 1 taken -> drop answer: [2, 127]
Because all jobs share the same duration, keeping a higher-profit job can never be worse than keeping a lower-profit one. So process jobs in decreasing profit.
Placing a job in the latest free slot <= deadline preserves the scarce early slots for jobs with tight deadlines — the exchange argument behind the greedy.
Scanning down from the deadline for a free slot is O(deadline) each. A disjoint-set that points each used slot to the next earlier free one finds it in near-O(1) amortized.
| Scan for a slot | Union-Find slots | |
|---|---|---|
| Idea | From the deadline, walk down to the first free slot | Jump straight to the latest free slot via DSU |
| Time | O(n log n + n * maxDeadline) | O(n log n + n * alpha) |
| Space | O(maxDeadline) | O(maxDeadline) |
Both sort by profit and place jobs late; the DSU replaces the per-job slot scan with a near-constant lookup. Full code is in the Approaches selector below.
Key takeaway
Sort jobs by profit descending and give each the latest free slot at or before its deadline. Scheduling late frees early slots for tight-deadline jobs — the exchange argument that makes this greedy optimal. A Union-Find over the slots turns the slot search into near-O(1).
sort jobs by profit descending
for each job [deadline, profit]:
find the latest free slot t <= deadline
if such t exists:
mark t used; count += 1; total += profit
return [count, total]