Job Sequencing Problem

Problem Statement

Given jobs with deadlines and profits, maximize profit by scheduling jobs within their deadlines. Each job takes 1 unit of time. This medium-level greedy problem is about prioritization—get the most bang for your buck!

Example

Input: jobs = [[1,4,20],[2,1,10],[3,1,40],[4,1,30]] (id, deadline, profit)

Output: 60 (schedule [3,1,40] at 1, [1,4,20] at 2)

Input: jobs = [[1,2,100],[2,1,19],[3,2,27]]

Output: 127

Code

public class Solution {
    public int jobScheduling(int[][] jobs) {
        Arrays.sort(jobs, (a, b) -> Integer.compare(b[2], a[2])); // Sort by profit
        int maxDeadline = 0;
        for (int[] job : jobs) maxDeadline = Math.max(maxDeadline, job[1]);
        boolean[] slots = new boolean[maxDeadline];
        int profit = 0;
        for (int[] job : jobs) {
            for (int j = Math.min(maxDeadline, job[1]) - 1; j >= 0; j--) {
                if (!slots[j]) {
                    slots[j] = true;
                    profit += job[2];
                    break;
                }
            }
        }
        return profit;
    }
}
            

def job_scheduling(jobs):
    jobs.sort(key=lambda x: x[2], reverse=True)  # Sort by profit
    max_deadline = max(job[1] for job in jobs)
    slots = [False] * max_deadline
    profit = 0
    for job in jobs:
        for j in range(min(max_deadline, job[1]) - 1, -1, -1):
            if not slots[j]:
                slots[j] = True
                profit += job[2]
                break
    return profit
            

function jobScheduling(jobs) {
    jobs.sort((a, b) => b[2] - a[2]); // Sort by profit
    const maxDeadline = Math.max(...jobs.map(job => job[1]));
    const slots = new Array(maxDeadline).fill(false);
    let profit = 0;
    for (let job of jobs) {
        for (let j = Math.min(maxDeadline, job[1]) - 1; j >= 0; j--) {
            if (!slots[j]) {
                slots[j] = true;
                profit += job[2];
                break;
            }
        }
    }
    return profit;
}
            

Explanation

• Greedy Choice: Sort by profit, schedule in the latest possible slot.
• Flow: Fill slots from right to left within deadlines.
• Example: [[1,4,20],[3,1,40]] → [40] at 1, [20] at 2.

Note