Problem
Each job takes one time slot and has a deadline and profit. Select and order jobs so that each finishes by its deadline and total profit is maximum.
Worked examples
Input: jobs = [("A",1,20),("B",2,50),("C",2,30)]
Output: 80
Run C then B. Both meet their deadlines.
Hints
Hint 1
Consider the most profitable jobs first.
Hint 2
Place a selected job as late as possible to leave earlier slots available.
Solution approach
- Sort jobs by decreasing profit. For each, search backward for an unused slot no later than its deadline.
- Assign the job if a slot exists; otherwise skip it. Clamp deadlines to n because no schedule needs more than n slots.
- A disjoint-set structure can make free-slot searches faster for large inputs.
Complexity
O(n log n + nD) for the simple method, D ≤ n; O(D) space.
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗