Job Sequencing Problem | Greedy Algorithm

1. Problem Statement & Overview

The Job Sequencing Problem is a classic optimization challenge in computer science where we are given a set of jobs, and our objective is to maximize total profit by completing as many jobs as possible before their respective deadlines.

Each job is characterized by three distinct attributes:

• Job ID: A unique identifier for the job.
• Deadline: The absolute last day by which the job must be completed. A deadline of $4$ means the job can be performed on day 1, day 2, day 3, or day 4—never beyond day 4.
• Profit: The financial reward or score gained upon successfully completing the job on or before its deadline.

Note:

• Each job takes exactly one day to complete.
• Only one job can be performed per day.
• You can choose any combination of jobs, provided they respect individual deadlines and time slots.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: The Freelancer's Deadline Strategy

Imagine you are a freelance developer with multiple incoming client projects. Each project pays a specific dollar amount (profit) and must be submitted by a strict calendar day (deadline). If you scramble to finish high-paying projects on their very first available days, you might block off early calendar slots and accidentally crowd out other urgent, shorter-deadline projects.

Instead, your optimal strategy is twofold:

1. Prioritize High Profit: Always look at the most lucrative jobs first so you don't miss out on big earnings.
2. Delay to the End (Just-in-Time Scheduling): Push jobs as close to their deadlines as possible. By scheduling jobs on the latest possible open day prior to their deadline, you keep all earlier days wide open and available for jobs that have much closer deadlines.

3. Naive vs. Better Approach

4. Step-by-Step Evolution of the Algorithm

To build our greedy scheduling engine, we follow a systematic four-step evolution:

1. Sort by Profit (Descending): Because our primary goal is profit maximization, we must evaluate jobs starting with the highest-paying down to the lowest-paying.
2. Find the Maximum Deadline: Scan through all jobs to identify the largest deadline value present. This determines the total timeline span we need to account for (e.g., a maximum deadline of $6$ means we need days $1$ through $6$).
3. Initialize an Availability Hash Array: Create an array of size $\text{MaxDeadline} + 1$ filled with -1 (representing empty, unallocated days).
4. Greedy Backward Placement: For each job, start checking backward from its deadline day down to day $1$. Place the job in the very first empty day (-1) you encounter.

5. Walkthrough of a Complete Example

Let us trace a sample job dataset to visualize how the greedy slotting mechanism operates.

Jobs Input:
- Job 1: Deadline 4, Profit 20
- Job 2: Deadline 5, Profit 60
- Job 3: Deadline 6, Profit 70
- Job 4: Deadline 6, Profit 65
- Job 5: Deadline 4, Profit 25
- Job 6: Deadline 2, Profit 80
- Job 7: Deadline 2, Profit 22
- Job 8: Deadline 4, Profit 20  (Assuming additional sample items)

Timeline Hash Array State Evolution

Initialize a hash array of size $7$ (indices $0$ to $6$), all set to -1:

Index:    [ 0,  1,  2,  3,  4,  5,  6 ]
Status:   [ -1, -1, -1, -1, -1, -1, -1 ]

1. Job 6 (Profit: 80, Deadline: 2):
   • Check day 2: Empty. Place Job 6 on day 2.
   • Profit = 80, Count = 1.
2. Job 3 (Profit: 70, Deadline: 6):
   • Check day 6: Empty. Place Job 3 on day 6.
   • Profit = 80 + 70 = 150, Count = 2.
3. Job 4 (Profit: 65, Deadline: 6):
   • Check day 6: Taken. Check day 5: Empty. Place Job 4 on day 5.
   • Profit = 150 + 65 = 215, Count = 3.
4. Job 2 (Profit: 60, Deadline: 5):
   • Check day 5: Taken. Check day 4: Empty. Place Job 2 on day 4.
   • Profit = 275, Count = 4.
5. Job 5 (Profit: 25, Deadline: 4):
   • Check day 4: Taken. Check day 3: Empty. Place Job 5 on day 3.
   • Profit = 300, Count = 5.

Final Hash Array Snapshot:
Day Index:  [ 0,    1,    2,    3,    4,    5,    6 ]
Assigned:   [ -1,  Day1, Job6, Job5, Job2, Job4, Job3 ]

6. Complete Implementation (C++)

Below is the clean, production-ready C++ implementation embodying the exact logic discussed in the lecture:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Structure representing a single Job
struct Job {
    int id;       // Job ID
    int profit;   // Profit earned if completed
    int deadline; // Deadline day
};

class Solution {
public:
    // Comparator function to sort jobs in descending order of profit
    static bool comparison(const Job& a, const Job& b) {
        return a.profit > b.profit;
    }

    // Function to return total jobs performed and maximum profit gained
    vector<int> JobScheduling(Job arr[], int n) {
        // Step 1: Sort jobs in descending order of profit
        sort(arr, arr + n, comparison);

        // Step 2: Find the maximum deadline to size our hash array
        int maxDeadline = 0;
        for (int i = 0; i < n; i++) {
            maxDeadline = max(maxDeadline, arr[i].deadline);
        }

        // Step 3: Create a hash array (slot tracker) initialized to -1
        vector<int> slot(maxDeadline + 1, -1);

        int countJobs = 0;
        int totalProfit = 0;

        // Step 4: Iterate through each job and find the latest available slot
        for (int i = 0; i < n; i++) {
            // Start from the job's deadline and check backwards to day 1
            for (int j = arr[i].deadline; j > 0; j--) {
                if (slot[j] == -1) { // Slot is free
                    slot[j] = arr[i].id; // Assign job ID to slot
                    countJobs++;
                    totalProfit += arr[i].profit;
                    break; // Move to the next job once scheduled
                }
            }
        }

        return {countJobs, totalProfit};
    }
};

int main() {
    Job arr[] = {{1, 20, 4}, {2, 60, 5}, {3, 70, 6}, {4, 65, 6}, {5, 25, 4}};
    int n = sizeof(arr) / sizeof(arr[0]);

    Solution obj;
    vector<int> ans = obj.JobScheduling(arr, n);

    cout << "Jobs Done: " << ans[0] << endl;
    cout << "Max Profit: " << ans[1] << endl;

    return 0;
}

7. Complexity Analysis

Advanced Optimization Note: In competitive programming, the inner linear scan for free slots can be optimized from $O(\text{MaxDeadline})$ down to $O(1)$ using a Disjoint Set Union (DSU) data structure. However, for standard interview settings, the nested loop approach shown above is completely expected and sufficient.

8. Summary and Key Takeaways

• Problem Goal: Maximize profit by scheduling jobs on individual days before their respective deadlines.
• Greedy Paradigm: Always greedily select jobs that yield the highest profit first.
• Just-in-Time Scheduling: Delay job execution as close to the deadline day as possible to keep early calendar slots available for tight deadlines.
• Sorting Requirement: Use a custom comparator to sort jobs in descending order of profit values.
• Tracking Array: Utilize a hash array initialized to -1 to keep track of occupied versus free calendar days.
• Time Performance: Dominated by sorting ($O(n \log n)$) and slot allocation lookup ($O(n \times \text{MaxDeadline})$).
• Return Signature: The algorithm outputs a pair consisting of the total number of jobs completed and the maximum accumulated profit.