Job Scheduling with Deadlines

Problem

Given jobs as [deadline, profit] pairs where each job takes one unit of time and only one job runs per slot, return the maximum total profit from jobs finished before their deadlines.

Sort jobs by descending profit and greedily place each in the latest free slot at or before its deadline, skipping jobs whose slots are all taken. Return 0 for no jobs.

Hint

Placing a high-profit job as late as possible keeps earlier slots free for tighter deadlines.

Test cases

case 1

in: [[[2,100],[1,19],[2,27],[1,25],[3,15]]]

expected: 142

case 2

in: [[[1,5],[1,10],[1,20]]]

expected: 20

case 3

in: [[[2,10],[1,5]]]

expected: 15

case 4

in: [[[1,1]]]

expected: 1

case 5

in: [[]]

expected: 0

Starter codePython

def job_scheduling_max_profit(jobs):
    # Your code here
    pass

5 test cases · run your code against them in the editor