Job Sequencing with Deadlines
Each job takes one unit of time and has a deadline and a profit; profit is earned only if the job is finished by its deadline. Only one job can run at a time. Choose and order jobs to maximise total profit.
- 1 ≤ n ≤ 10^5
- 1 ≤ deadline[i] ≤ n
- 1 ≤ profit[i] ≤ 10^9
- Unit-time jobs with deadlines → time slots are the resource
- Most profitable job first, placed as late as possible
- Finding the latest free slot ≤ deadline is a union-find query
When a locally best choice (earliest finish time, largest ratio, farthest reach) can be proved never to hurt the global optimum, you can commit to it without exploring alternatives and get O(n log n) from sorting. The proof usually comes via an exchange argument; if you cannot sketch one, suspect DP instead.
Sort jobs by profit in descending order. For each job, find the latest free slot at or before its deadline and assign the job there; if none exists, skip it. Placing each job as late as possible preserves earlier slots for jobs with tighter deadlines. A disjoint-set structure over slots, where each slot points to the nearest free slot to its left, makes each lookup nearly constant.
- A linear scan for a free slot per job is O(n^2). Sorting by deadline and using a min-heap of chosen profits that evicts the smallest when a deadline is violated is an equivalent greedy.