Job sequencing with deadlines (maximise profit)

Medium

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}

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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]).