Job sequencing with deadlines (maximise profit)
Problem
Each job takes one unit of time and has a deadline and a profit. Schedule jobs, one at a time, so that each finishes by its deadline and the total profit is maximised. Return the number of jobs done and the profit.
Example 1
Input: jobs (deadline, profit) = [(4,20), (1,10), (1,40), (1,30)] Output: 2 jobs, profit 60
Also asked as: Job SequencingProblem · Weighted Job Scheduling
Test cases
Case 1
Input: [{"id":1,"deadline":4,"profit":20},{"id":2,"deadline":1,"profit":10},{"id":3,"deadline":1,"profit":40},{"id":4,"deadline":1,"profit":30}]
Expected: {"count":2,"profit":60}Case 2
Input: [{"id":1,"deadline":2,"profit":100},{"id":2,"deadline":1,"profit":19},{"id":3,"deadline":2,"profit":27},{"id":4,"deadline":1,"profit":25},{"id":5,"deadline":1,"profit":15}]
Expected: {"count":2,"profit":127}Case 3
Input: [{"id":1,"deadline":1,"profit":5},{"id":2,"deadline":1,"profit":9}]
Expected: {"count":1,"profit":9}Case 4
Input: [{"id":1,"deadline":3,"profit":7}]
Expected: {"count":1,"profit":7}View solutionHide solution1 approach
1. Sort by profit desc, place each job in the latest free slot ≤ its deadline
Time O(n log n + n·maxDeadline)Space O(maxDeadline)
High-profit jobs first; give each the last available day before its deadline (a DSU of "next free slot" makes slot-finding near O(1)).
function jobSequencing(jobs) { // {id, deadline, profit} jobs.sort((a, b) => b.profit - a.profit); const maxD = Math.max(...jobs.map((j) => j.deadline)); const slot = new Array(maxD + 1).fill(null); let profit = 0, count = 0; for (const j of jobs) { for (let d = j.deadline; d >= 1; d--) { if (!slot[d]) { slot[d] = j.id; profit += j.profit; count++; break; } } } return { count, profit };}Weighted Job Scheduling where jobs may overlap and you want max total profit is DP: sort by end time, dp[i] = max(dp[i-1], profit[i] + dp[last non-conflicting]).