Searching & SortingProblem 27 of 36

Job Scheduling Algo

Brute Force
Time: O(n! * n)
Space: O(n)
Optimal
Time: O(n log n)
Space: O(n)

Problem Statement

Given a set of N jobs where each job has a deadline and profit associated with it. Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit if and only if the job is completed by its deadline. Find the maximum number of jobs that can be done and the maximum profit.

Constraints:

  • 1 ≤ N ≤ 10^5
  • 1 ≤ Deadline ≤ N
  • 1 ≤ Profit ≤ 500

Example:

  • Input: jobs = [(1, 4, 20), (2, 1, 10), (3, 1, 40), (4, 1, 30)] (id, deadline, profit)
  • Output: 2 jobs, profit = 60
  • Explanation: Job 3 at slot 1, Job 1 at slot 4. Or Job 3 at slot 1, Job 1 at slots 2-4.

Example 2:

  • Input: jobs = [(1, 2, 100), (2, 1, 19), (3, 2, 27), (4, 1, 25), (5, 1, 15)]
  • Output: 2 jobs, profit = 127
  • Explanation: Job 1 (profit=100) at slot 2, Job 3 (profit=27) at slot 1

Approach 1: Brute Force (Try All Permutations)

Intuition

Try all possible permutations of jobs and for each permutation, schedule jobs greedily. Track the maximum profit across all permutations.

Algorithm

  1. Generate all permutations of jobs
  2. For each permutation, try to schedule jobs in order
  3. A job is scheduled if its deadline slot or any earlier slot is free
  4. Track maximum profit
java
import java.util.*;

public class Solution {
    static class Job {
        int id, deadline, profit;
        Job(int id, int deadline, int profit) {
            this.id = id;
            this.deadline = deadline;
            this.profit = profit;
        }
    }
    
    private void permute(Job[] jobs, int l, int r, int[] result) {
        if (l == r) {
            int[] res = scheduleJobs(jobs);
            if (res[1] > result[1]) {
                result[0] = res[0];
                result[1] = res[1];
            }
            return;
        }
        
        for (int i = l; i <= r; i++) {
            swap(jobs, l, i);
            permute(jobs, l + 1, r, result);
            swap(jobs, l, i);
        }
    }
    
    private int[] scheduleJobs(Job[] jobs) {
        int n = jobs.length;
        boolean[] slot = new boolean[n + 1];
        int profit = 0, count = 0;
        
        for (Job job : jobs) {
            for (int j = Math.min(n, job.deadline); j >= 1; j--) {
                if (!slot[j]) {
                    slot[j] = true;
                    profit += job.profit;
                    count++;
                    break;
                }
            }
        }
        
        return new int[]{count, profit};
    }
    
    private void swap(Job[] jobs, int i, int j) {
        Job temp = jobs[i];
        jobs[i] = jobs[j];
        jobs[j] = temp;
    }
}

Complexity Analysis

  • Time Complexity: O(n! × n) - n! permutations, O(n) to schedule each
  • Space Complexity: O(n) - For slot array

Approach 2: Greedy with Sorting (Optimal)

Intuition

Sort jobs by profit in decreasing order. For each job, try to schedule it in the latest available slot before its deadline. This greedy approach works because:

  1. Higher profit jobs are considered first
  2. Scheduling at the latest slot leaves earlier slots for other jobs

Algorithm

  1. Sort jobs by profit in decreasing order
  2. Create a slot array of size max(deadline)
  3. For each job, find the latest free slot ≤ deadline
  4. If found, schedule the job and add profit
java
import java.util.*;

public class JobScheduling {
    static class Job {
        int id, deadline, profit;
        
        Job(int id, int deadline, int profit) {
            this.id = id;
            this.deadline = deadline;
            this.profit = profit;
        }
    }
    
    public int[] jobScheduling(Job[] jobs) {
        int n = jobs.length;
        
        // Sort by profit in decreasing order
        Arrays.sort(jobs, (a, b) -> b.profit - a.profit);
        
        // Find maximum deadline
        int maxDeadline = 0;
        for (Job job : jobs) {
            maxDeadline = Math.max(maxDeadline, job.deadline);
        }
        
        // Slot array (-1 means empty)
        int[] slot = new int[maxDeadline + 1];
        Arrays.fill(slot, -1);
        
        int jobCount = 0;
        int totalProfit = 0;
        
        for (Job job : jobs) {
            // Find the latest available slot
            for (int j = job.deadline; j >= 1; j--) {
                if (slot[j] == -1) {
                    slot[j] = job.id;
                    jobCount++;
                    totalProfit += job.profit;
                    break;
                }
            }
        }
        
        return new int[]{jobCount, totalProfit};
    }
    
    public static void main(String[] args) {
        JobScheduling js = new JobScheduling();
        Job[] jobs = {
            new Job(1, 4, 20),
            new Job(2, 1, 10),
            new Job(3, 1, 40),
            new Job(4, 1, 30)
        };
        
        int[] result = js.jobScheduling(jobs);
        System.out.println("Jobs: " + result[0] + ", Profit: " + result[1]);
    }
}

Dry Run Example

jobs = [(1, 4, 20), (2, 1, 10), (3, 1, 40), (4, 1, 30)] Step 1: Sort by profit descending sorted = [(3, 1, 40), (4, 1, 30), (1, 4, 20), (2, 1, 10)] Step 2: Initialize slots maxDeadline = 4 slot = [-1, -1, -1, -1, -1] (indices 0-4) Step 3: Process each job Job (3, 1, 40): deadline = 1 Check slot[1]: empty slot[1] = 3 jobCount = 1, profit = 40 slot = [-1, 3, -1, -1, -1] Job (4, 1, 30): deadline = 1 Check slot[1]: occupied No free slot found slot = [-1, 3, -1, -1, -1] Job (1, 4, 20): deadline = 4 Check slot[4]: empty slot[4] = 1 jobCount = 2, profit = 60 slot = [-1, 3, -1, -1, 1] Job (2, 1, 10): deadline = 1 Check slot[1]: occupied No free slot found Result: Jobs = 2, Profit = 60 Scheduled: Job 3 at slot 1, Job 1 at slot 4

Complexity Analysis

  • Time Complexity: O(n² ) - Sorting O(n log n) + O(n × maxDeadline) for scheduling
  • Space Complexity: O(maxDeadline) - For slot array

Approach 3: Greedy with Disjoint Set Union (Most Optimal)

Intuition

Use Union-Find (DSU) to efficiently find the latest available slot. Each slot points to the next available slot to its left. This eliminates the linear search in the basic greedy approach.

Algorithm

  1. Sort jobs by profit
  2. Use DSU where parent[i] = latest available slot ≤ i
  3. For each job, find available slot using find(deadline)
  4. Union the slot with slot-1 after scheduling
java
import java.util.*;

public class JobSchedulingDSU {
    private int[] parent;
    
    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // Path compression
        }
        return parent[x];
    }
    
    public int[] schedule(int[][] jobs) {
        // Sort by profit descending
        Arrays.sort(jobs, (a, b) -> b[2] - a[2]);
        
        // Find max deadline
        int maxDeadline = 0;
        for (int[] job : jobs) {
            maxDeadline = Math.max(maxDeadline, job[1]);
        }
        
        // Initialize DSU
        parent = new int[maxDeadline + 1];
        for (int i = 0; i <= maxDeadline; i++) {
            parent[i] = i;
        }
        
        int jobCount = 0;
        int totalProfit = 0;
        
        for (int[] job : jobs) {
            int deadline = job[1];
            int profit = job[2];
            
            // Find latest available slot
            int availableSlot = find(deadline);
            
            if (availableSlot > 0) {
                // Schedule the job
                jobCount++;
                totalProfit += profit;
                
                // Union with left slot
                parent[availableSlot] = find(availableSlot - 1);
            }
        }
        
        return new int[]{jobCount, totalProfit};
    }
    
    public static void main(String[] args) {
        JobSchedulingDSU js = new JobSchedulingDSU();
        int[][] jobs = {{1, 4, 20}, {2, 1, 10}, {3, 1, 40}, {4, 1, 30}};
        int[] result = js.schedule(jobs);
        System.out.println("Jobs: " + result[0] + ", Profit: " + result[1]);
    }
}

Complexity Analysis (DSU Approach)

  • Time Complexity: O(n log n + n × α(n)) ≈ O(n log n)
    • Sorting: O(n log n)
    • DSU operations: O(α(n)) per operation (near constant)
  • Space Complexity: O(maxDeadline) - For parent array

Key Takeaways

  1. Greedy Strategy: Process jobs in decreasing order of profit
  2. Latest Slot First: Always try to schedule at the latest possible slot to maximize opportunities for other jobs
  3. DSU Optimization: Use Disjoint Set Union for O(α(n)) slot finding instead of O(n) linear search
  4. Deadline Constraint: A job can be scheduled in any slot from 1 to its deadline
  5. No Preemption: Each job must be completed in a single unit of time
  6. Proof of Greedy: Higher profit jobs have priority; later slots are preferred to leave room for jobs with earlier deadlines
  7. Space Optimization: Slot array size depends on maximum deadline, not number of jobs
Previous
EKOSPOJ
Next
Missing Number in AP