Job Sequencing Problem

Given an array of jobs where every job has a deadline and associated profit, find the sequence of jobs that maximizes total profit. Each job takes a single unit of time, and the minimum deadline for any job is 1. Only one job can be scheduled at a time.

Greedy Approach

The greedy strategy is to perform the highest-profit jobs first.

To maximize the opportunity for scheduling other jobs, we should schedule each job as late as possible—specifically at its deadline or in the latest available free time slot before its deadline.

Algorithm Steps

Sort all jobs in descending order of their profit.
Find the maximum deadline among all jobs. Create a slots array of that size, initialized to empty/false, to keep track of filled time slots.
Iterate through each job in the sorted list:
- Search for a free slot from min(maxDeadline, job.deadline) - 1 down to 0.
- If a free slot is found, assign the job to that slot, mark it filled, and move to the next job.
- If no slot is free, ignore the job.

Examples

Example 1

Input:
- Job A: Deadline = 4, Profit = 20
- Job B: Deadline = 1, Profit = 10
- Job C: Deadline = 1, Profit = 40
- Job D: Deadline = 1, Profit = 30
Sorted by Profit: C (40), D (30), A (20), B (10)
Trace:
- Maximum deadline is 4. Slots available: [0, 1, 2, 3] (representing times 1, 2, 3, 4).
- Process C (DL 1): Assign to slot 0 (time 1). Slots: [C, false, false, false].
- Process D (DL 1): Slot 0 is taken. Ignore.
- Process A (DL 4): Assign to slot 3 (time 4). Slots: [C, false, false, A].
- Process B (DL 1): Slot 0 is taken. Ignore.
Output: Sequence is C, A. Total profit = 60.

Example 2

Input:
- Job A: Deadline = 2, Profit = 100
- Job B: Deadline = 1, Profit = 19
- Job C: Deadline = 2, Profit = 27
- Job D: Deadline = 1, Profit = 25
- Job E: Deadline = 3, Profit = 15
Sorted by Profit: A (100), C (27), D (25), B (19), E (15)
Trace:
- Max deadline is 3. Slots available: [0, 1, 2].
- Process A (DL 2): Assign to slot 1 (time 2). Slots: [false, A, false].
- Process C (DL 2): Slot 1 is taken. Slot 0 is free $\rightarrow$ Assign to slot 0 (time 1). Slots: [C, A, false].
- Process D (DL 1): Slot 0 is taken. Ignore.
- Process B (DL 1): Slot 0 is taken. Ignore.
- Process E (DL 3): Assign to slot 2 (time 3). Slots: [C, A, E].
Output: Sequence is C, A, E. Total profit = 142.

JavaScript Code Implementation

class Job {
    constructor(id, deadline, profit) {
        this.id = id;
        this.deadline = deadline;
        this.profit = profit;
    }
}
 
function printJobScheduling(jobs) {
    // 1. Sort all jobs in descending order of profit
    jobs.sort((a, b) => b.profit - a.profit);
 
    const n = jobs.length;
    
    // 2. Find max deadline to size the slots array
    let maxDeadline = 0;
    for (let job of jobs) {
        if (job.deadline > maxDeadline) {
            maxDeadline = job.deadline;
        }
    }
 
    // 3. Initialize slots and result tracking
    const result = new Array(maxDeadline).fill(null);
    const slot = new Array(maxDeadline).fill(false);
 
    let totalProfit = 0;
 
    // 4. Iterate through all sorted jobs
    for (let i = 0; i < n; i++) {
        // Find a free slot for this job (starting from the latest possible slot)
        const limit = Math.min(maxDeadline, jobs[i].deadline) - 1;
        for (let j = limit; j >= 0; j--) {
            if (!slot[j]) {
                slot[j] = true;
                result[j] = jobs[i].id;
                totalProfit += jobs[i].profit;
                break;
            }
        }
    }
 
    // Filter out unfilled slots and print
    const finalSequence = result.filter(id => id !== null);
    
    return {
        sequence: finalSequence,
        profit: totalProfit
    };
}
 
// Driver code matching Example 2
const jobs = [
    new Job("a", 2, 100),
    new Job("b", 1, 19),
    new Job("c", 2, 27),
    new Job("d", 1, 25),
    new Job("e", 3, 15)
];
 
const result = printJobScheduling(jobs);
console.log("Following is maximum profit sequence of jobs:", result.sequence.join(", "));
console.log("Total Profit:", result.profit);
/*
Output:
Following is maximum profit sequence of jobs: c, a, e
Total Profit: 142
*/

Complexity Analysis

Time Complexity: O(N^2)
- Sorting the jobs takes O(N log N) time.
- The nested loops for placing each job in a free slot take up to O(N * maxDeadline) time, which is O(N^2) in the worst case.
- Note: This can be optimized to O(N log N) using a Disjoint Set (Union-Find) data structure to find available slots in near-constant time.
Auxiliary Space: O(N)
- To store the slots and output tracking arrays.

Fractional Knapsack Huffman Coding