Job Scheduling with Deadlines

LeetCode #1235 [Hard]

Problem Statement

Schedule jobs to maximize total profit, each with a deadline and profit.

Example: Jobs = [(a,2,100),(b,1,19),(c,2,27)], Output: Maximum profit = 127

Approach 1: Brute Force

Try all permutations of jobs and select feasible schedule with max profit.

for each permutation of jobs:
    if schedule is feasible (no overlapping deadlines):
        calculate profit
return maximum profit

💡 Think: Try all job orders and keep the feasible schedule with maximum profit.

Approach 2: Better

Sort by deadline and schedule recursively.

sort jobs by deadline
profit = 0
for each job:
    assign to latest available slot before deadline
    profit += job.profit if slot available
return profit

💡 Think: Order by deadline and attempt to place each job backward into a free slot.

Approach 3: Optimal Greedy

Sort jobs by profit descending, assign latest available slot before deadline.

sort jobs by profit descending
initialize slots array
for each job:
    for j = min(deadline, n) downto 1:
        if slot[j] is free:
            assign job
            totalProfit += job.profit
            break
return totalProfit

💡 Think: Sort by profit desc; place each job in the latest free slot ≤ its deadline.

Solve on LeetCode