GreedyProblem 2 of 35

Job Sequencing Problem

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

Problem Statement

Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. Every job takes a single unit of time, and only one job can be scheduled at a time. Maximize the total profit by scheduling jobs optimally.

Constraints:

  • 1 ≤ n ≤ 10^5
  • 1 ≤ deadline[i] ≤ n
  • 1 ≤ profit[i] ≤ 10^5

Example:

  • Input: jobs = [(1, 4, 20), (2, 1, 10), (3, 1, 40), (4, 1, 30)] (id, deadline, profit)
  • Output: 2 jobs, 60 profit
  • Explanation: Jobs 3 and 1 are selected with profits 40 and 20.

Example 2:

  • Input: jobs = [(1, 2, 100), (2, 1, 19), (3, 2, 27), (4, 1, 25), (5, 1, 15)]
  • Output: 2 jobs, 127 profit
  • Explanation: Jobs 1 and 3 are selected.

Approach 1: Brute Force (Try All Permutations)

Intuition

Generate all possible sequences of jobs and find the one that gives maximum profit while respecting deadlines.

Algorithm

  1. Generate all permutations of jobs
  2. For each permutation, greedily assign jobs to earliest available slots
  3. Calculate profit for valid assignments
  4. Track maximum profit
java
import java.util.*;

public class Solution {
    private int maxProfit = 0;
    private int maxJobs = 0;
    
    private void tryAllPermutations(int[][] jobs, boolean[] used, 
                                    boolean[] slots, int profit, int count) {
        if (profit > maxProfit) {
            maxProfit = profit;
            maxJobs = count;
        }
        
        for (int i = 0; i < jobs.length; i++) {
            if (!used[i]) {
                used[i] = true;
                int deadline = jobs[i][1];
                int jobProfit = jobs[i][2];
                
                // Try to find a slot
                for (int slot = deadline - 1; slot >= 0; slot--) {
                    if (!slots[slot]) {
                        slots[slot] = true;
                        tryAllPermutations(jobs, used, slots, 
                                          profit + jobProfit, count + 1);
                        slots[slot] = false;
                        break;
                    }
                }
                
                // Also try skipping this job
                tryAllPermutations(jobs, used, slots, profit, count);
                used[i] = false;
            }
        }
    }
    
    public int[] jobSequencing(int[][] jobs) {
        int n = jobs.length;
        int maxDeadline = 0;
        for (int[] job : jobs) {
            maxDeadline = Math.max(maxDeadline, job[1]);
        }
        
        boolean[] used = new boolean[n];
        boolean[] slots = new boolean[maxDeadline];
        maxProfit = 0;
        maxJobs = 0;
        tryAllPermutations(jobs, used, slots, 0, 0);
        return new int[]{maxJobs, maxProfit};
    }
}

Complexity Analysis

  • Time Complexity: O(n! * n) - n! permutations, each taking O(n) to process
  • Space Complexity: O(n) - For slots array and recursion stack

Approach 2: Greedy (Sort by Profit) - Optimal

Intuition

Greedy approach: Process jobs in decreasing order of profit. For each job, schedule it in the latest available slot before its deadline.

Key Insight: Higher profit jobs should be prioritized. By assigning to the latest available slot, we keep earlier slots free for jobs with earlier deadlines.

Algorithm

  1. Sort jobs by profit in decreasing order
  2. For each job, find the latest free slot before deadline
  3. If slot found, schedule the job
  4. Sum up profits
java
import java.util.*;

public class JobSequencing {
    public int[] schedule(int[][] jobs) {
        int n = jobs.length;
        
        // Sort by profit in descending order
        Arrays.sort(jobs, (a, b) -> b[2] - a[2]);
        
        // Find maximum deadline
        int maxDeadline = 0;
        for (int[] job : jobs) {
            maxDeadline = Math.max(maxDeadline, job[1]);
        }
        
        // Slot array: -1 means free
        int[] slots = new int[maxDeadline];
        Arrays.fill(slots, -1);
        
        int totalProfit = 0;
        int jobCount = 0;
        
        for (int[] job : jobs) {
            int id = job[0];
            int deadline = job[1];
            int profit = job[2];
            
            // Find latest free slot before deadline
            for (int slot = deadline - 1; slot >= 0; slot--) {
                if (slots[slot] == -1) {
                    slots[slot] = id;
                    totalProfit += profit;
                    jobCount++;
                    break;
                }
            }
        }
        
        return new int[]{jobCount, totalProfit};
    }
    
    public List<Integer> getSchedule(int[][] jobs) {
        int n = jobs.length;
        
        Arrays.sort(jobs, (a, b) -> b[2] - a[2]);
        
        int maxDeadline = 0;
        for (int[] job : jobs) {
            maxDeadline = Math.max(maxDeadline, job[1]);
        }
        
        int[] slots = new int[maxDeadline];
        Arrays.fill(slots, -1);
        
        for (int[] job : jobs) {
            int id = job[0];
            int deadline = job[1];
            
            for (int slot = deadline - 1; slot >= 0; slot--) {
                if (slots[slot] == -1) {
                    slots[slot] = id;
                    break;
                }
            }
        }
        
        List<Integer> result = new ArrayList<>();
        for (int id : slots) {
            if (id != -1) result.add(id);
        }
        return result;
    }
    
    public static void main(String[] args) {
        JobSequencing js = new JobSequencing();
        int[][] jobs = {{1, 4, 20}, {2, 1, 10}, {3, 1, 40}, {4, 1, 30}};
        int[] result = js.schedule(jobs);
        System.out.println(result[0] + " jobs, " + result[1] + " profit");  // 2 jobs, 60 profit
    }
}

Dry Run Example

Jobs: [(1, 4, 20), (2, 1, 10), (3, 1, 40), (4, 1, 30)] After sorting by profit (descending): [(3, 1, 40), (4, 1, 30), (1, 4, 20), (2, 1, 10)] Max deadline = 4 Slots: [_, _, _, _] (indices 0, 1, 2, 3) Step 1: Job 3 (deadline=1, profit=40) - Try slot 0: free, assign! - Slots: [3, _, _, _] - Profit = 40, Count = 1 Step 2: Job 4 (deadline=1, profit=30) - Try slot 0: occupied by Job 3 - No free slot before deadline 1 - Slots: [3, _, _, _] - Profit = 40, Count = 1 Step 3: Job 1 (deadline=4, profit=20) - Try slot 3: free, assign! - Slots: [3, _, _, 1] - Profit = 60, Count = 2 Step 4: Job 2 (deadline=1, profit=10) - Try slot 0: occupied - No free slot - Slots: [3, _, _, 1] Result: 2 jobs, profit = 60 Schedule: Job 3 at t=0, Job 1 at t=3

Complexity Analysis

  • Time Complexity: O(n log n + n * m) where m is max deadline
    • O(n log n) for sorting
    • O(n * m) for slot assignment in worst case
  • Space Complexity: O(m) - For slots array

Approach 3: Using Disjoint Set Union (DSU) - Further Optimization

Intuition

Use DSU to quickly find the latest available slot. Each slot points to the next available slot.

Time Complexity: O(n log n + n * α(n)) ≈ O(n log n)

Key Takeaways

  1. Greedy by Profit: Sort jobs by profit in descending order
  2. Latest Slot: Assign job to latest available slot before deadline
  3. Why Latest? Keeps earlier slots free for jobs with earlier deadlines
  4. Each Job = 1 Unit Time: Critical constraint for this problem
  5. DSU Optimization: Can optimize slot finding from O(m) to O(α(n))
  6. Deadline Slots: Create m slots where m = max deadline
  7. Similar Problems: Weighted Job Scheduling, Task Scheduler
Previous
Activity Selection Problem
Next
Huffman Coding