Job Scheduling with Deadlines in DSA C++

Mental Model

We want to schedule jobs so that we finish as many as possible before their deadlines, choosing the most profitable jobs first.

Analogy: Imagine you have a list of tasks to do before certain times, and each task gives you some money. You want to pick tasks that pay the most and still finish on time, like picking the best gigs before their deadlines.

Jobs: [Job1: profit=20, deadline=2]
       [Job2: profit=15, deadline=2]
       [Job3: profit=10, deadline=1]
       [Job4: profit=5, deadline=3]
       [Job5: profit=1, deadline=3]

Schedule slots: [ _ ] -> time 1
                [ _ ] -> time 2
                [ _ ] -> time 3

Dry Run Walkthrough

Input: Jobs: (profit, deadline) = [(20,2), (15,2), (10,1), (5,3), (1,3)]

Goal: Schedule jobs to maximize total profit without missing deadlines

Step 1: Sort jobs by profit descending

Jobs sorted: (20,2), (15,2), (10,1), (5,3), (1,3)

Why: We want to pick the most profitable jobs first to maximize earnings

Step 2: Schedule job (20,2) at latest free slot before deadline 2 -> slot 2

Schedule: [ _ ] -> time 1
          [20] -> time 2
          [ _ ] -> time 3

Why: Slot 2 is free and before deadline, so assign job here

Step 3: Schedule job (15,2) at latest free slot before deadline 2 -> slot 1

Schedule: [15] -> time 1
          [20] -> time 2
          [ _ ] -> time 3

Why: Slot 2 is taken, so assign job to slot 1 which is free and before deadline

Step 4: Try to schedule job (10,1) at slot 1 but it's taken, so skip

Schedule unchanged: [15] -> time 1
                     [20] -> time 2
                     [ _ ] -> time 3

Why: No free slot before deadline 1, so cannot schedule this job

Step 5: Schedule job (5,3) at latest free slot before deadline 3 -> slot 3

Schedule: [15] -> time 1
          [20] -> time 2
          [5]  -> time 3

Why: Slot 3 is free and before deadline, so assign job here

Step 6: Try to schedule job (1,3) but all slots before deadline 3 are taken, so skip

Schedule unchanged: [15] -> time 1
                     [20] -> time 2
                     [5]  -> time 3

Why: No free slot before deadline 3, so cannot schedule this job

Result:

Final schedule: 15 -> 20 -> 5 -> null
Total profit: 40

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Job {
    int profit;
    int deadline;
};

bool compareProfit(Job a, Job b) {
    return a.profit > b.profit; // sort descending by profit
}

void jobScheduling(vector<Job>& jobs) {
    sort(jobs.begin(), jobs.end(), compareProfit); // pick high profit first

    int maxDeadline = 0;
    for (auto& job : jobs) {
        if (job.deadline > maxDeadline) maxDeadline = job.deadline; // find max deadline
    }

    vector<int> schedule(maxDeadline + 1, -1); // slots: index 1..maxDeadline

    int totalProfit = 0;

    for (auto& job : jobs) {
        for (int slot = job.deadline; slot > 0; slot--) {
            if (schedule[slot] == -1) { // free slot found
                schedule[slot] = job.profit; // assign job
                totalProfit += job.profit;
                break; // move to next job
            }
        }
    }

    // print schedule
    for (int i = 1; i <= maxDeadline; i++) {
        if (schedule[i] != -1) cout << schedule[i] << " -> ";
    }
    cout << "null" << endl;
    cout << "Total profit: " << totalProfit << endl;
}

int main() {
    vector<Job> jobs = {{20,2}, {15,2}, {10,1}, {5,3}, {1,3}};
    jobScheduling(jobs);
    return 0;
}

sort(jobs.begin(), jobs.end(), compareProfit);

sort jobs by profit descending to prioritize high profit jobs

for (auto& job : jobs) { if (job.deadline > maxDeadline) maxDeadline = job.deadline; }

find maximum deadline to size schedule slots

vector<int> schedule(maxDeadline + 1, -1);

initialize schedule slots as free (-1) indexed by time

for (auto& job : jobs) { for (int slot = job.deadline; slot > 0; slot--) { if (schedule[slot] == -1) { schedule[slot] = job.profit; totalProfit += job.profit; break; } } }

assign each job to latest free slot before deadline to maximize profit

for (int i = 1; i <= maxDeadline; i++) { if (schedule[i] != -1) cout << schedule[i] << " -> "; }

print scheduled jobs in order of time slots

Output

20 -> 15 -> 5 -> null

Total profit: 40

Complexity Analysis

Time: O(n log n) because we sort the jobs by profit and then for each job we scan slots up to its deadline

Space: O(n) for storing jobs and schedule slots

vs Alternative: Compared to brute force checking all permutations (O(n!)), this greedy approach is efficient and practical

Edge Cases

No jobs

Output is empty schedule and zero profit

DSA C++

for (auto& job : jobs) { if (job.deadline > maxDeadline) maxDeadline = job.deadline; }

All jobs have the same deadline

Only the most profitable jobs fitting in available slots are scheduled

DSA C++

for (int slot = job.deadline; slot > 0; slot--) { if (schedule[slot] == -1) {

Jobs with deadlines larger than number of jobs

Schedule size adapts to max deadline, allowing more slots if available

DSA C++

int maxDeadline = 0; for (auto& job : jobs) { if (job.deadline > maxDeadline) maxDeadline = job.deadline; }

When to Use This Pattern

When you see tasks with deadlines and profits and need to maximize total profit by scheduling, use the greedy job scheduling pattern to assign jobs to latest free slots before their deadlines.

Common Mistakes

Mistake: Assigning jobs to earliest free slot instead of latest free slot before deadline
Fix: Assign jobs starting from their deadline slot backwards to find the latest free slot

Mistake: Not sorting jobs by profit descending before scheduling
Fix: Sort jobs by profit descending to prioritize high profit jobs first

Summary

Schedules jobs to maximize total profit without missing deadlines.

Use when you have jobs with deadlines and profits and want the best profit schedule.

Sort jobs by profit and assign each to the latest free slot before its deadline.

Practice

1. What is the main goal of the Job Scheduling with Deadlines problem?

easy

A. Minimize the number of jobs scheduled

B. Schedule jobs in the order they appear without considering deadlines

C. Maximize total profit by scheduling jobs before their deadlines

D. Maximize the number of jobs scheduled regardless of profit

Solution

1. Step 1: Understand the problem objective

   The problem aims to schedule jobs so that each job finishes before its deadline to earn profit.

2. Step 2: Identify the optimization goal

   The goal is to maximize the total profit earned by selecting jobs that fit within their deadlines.

3. Final Answer:

   Maximize total profit by scheduling jobs before their deadlines -> Option C

4. Quick Check:

   Goal = Maximize profit [OK]

Hint: Focus on profit maximization within deadlines [OK]

Common Mistakes:

• Ignoring deadlines and scheduling all jobs
• Trying to schedule jobs in input order
• Maximizing number of jobs instead of profit

2. Which of the following is the correct C++ syntax to sort jobs by profit in descending order using std::sort and a custom comparator?

easy

A. std::sort(jobs.begin(), jobs.end());

B. std::sort(jobs.begin(), jobs.end(), [](Job a, Job b){ return a.profit > b.profit; });

C. std::sort(jobs.begin(), jobs.end(), compare); // where compare returns a.profit < b.profit

D. std::sort(jobs.begin(), jobs.end(), [](Job a, Job b){ return a.profit < b.profit; });

Solution

1. Step 1: Understand sorting by profit descending

   To sort descending, comparator should return true if first profit is greater than second.

2. Step 2: Check lambda comparator syntax

   std::sort(jobs.begin(), jobs.end(), [](Job a, Job b){ return a.profit > b.profit; }); uses a lambda returning a.profit > b.profit, which sorts descending correctly.

3. Final Answer:

   std::sort(jobs.begin(), jobs.end(), [](Job a, Job b){ return a.profit > b.profit; }); -> Option B

4. Quick Check:

   Descending sort = a.profit > b.profit [OK]

Hint: Use comparator returning true if first > second for descending [OK]

Common Mistakes:

• Using < instead of > for descending order
• Not providing a comparator for custom sorting
• Using default sort which sorts ascending

3. Given jobs with deadlines and profits:
jobs = [{id:1, deadline:2, profit:100}, {id:2, deadline:1, profit:19}, {id:3, deadline:2, profit:27}, {id:4, deadline:1, profit:25}, {id:5, deadline:3, profit:15}]
What is the maximum profit achievable by scheduling these jobs?

medium

A. 185

B. 190

C. 160

D. 142

Solution

1. Step 1: Sort jobs by profit descending

   Sorted jobs: (1,100,2), (3,27,2), (4,25,1), (2,19,1), (5,15,3)

2. Step 2: Schedule jobs greedily before deadlines

   Schedule job 1 at slot 2, job 4 at slot 1, job 5 at slot 3. Jobs 3 and 2 cannot fit without conflict.

3. Step 3: Calculate total profit

   Profit = 100 + 25 + 15 = 140. But check if job 3 can replace job 4 for better profit: job 3 (27) > job 4 (25), so schedule job 3 at slot 2, job 4 at slot 1 is not possible because slot 1 is taken by job 4. Instead, schedule job 3 at slot 2, job 2 at slot 1 (profit 19), job 5 at slot 3 (15). Total = 100 + 27 + 15 = 142. Better is job 1 (100), job 3 (27), job 4 (25) at slots 2,1,3 respectively? Slot 3 deadline is 3, so job 4 deadline 1 can't be at 3. So best is job 1 (100), job 3 (27), job 4 (25) at slots 2,1, no slot for job 5. Total 152. Actually, slot 3 is free for job 5 (15). So schedule job 1 at 2, job 4 at 1, job 5 at 3 = 100+25+15=140. Or job 1 at 2, job 3 at 1, job 5 at 3 = 100+27+15=142. Or job 1 at 2, job 4 at 1, job 3 can't fit. So max profit is 142.

4. Final Answer:

   142 -> Option D

5. Quick Check:

   Max profit = 142 [OK]

Hint: Sort by profit, schedule greedily before deadlines [OK]

Common Mistakes:

• Scheduling jobs ignoring deadlines
• Not sorting by profit first
• Overlapping jobs in same time slot

4. Identify the error in the following C++ code snippet for job scheduling:

struct Job { int id, deadline, profit; };
std::vector<Job> jobs = ...;
std::sort(jobs.begin(), jobs.end(), [](Job a, Job b){ return a.profit < b.profit; });
std::vector<int> slot(maxDeadline + 1, -1);
for (auto &job : jobs) {
  for (int j = job.deadline; j > 0; j--) {
    if (slot[j] == -1) {
      slot[j] = job.id;
      break;
    }
  }
}

medium

A. Sorting comparator sorts ascending instead of descending

B. Slots vector size should be maxDeadline, not maxDeadline + 1

C. Inner loop should run from 1 to job.deadline, not reverse

D. Job IDs should not be stored in slots, profits should be stored

Solution

1. Step 1: Analyze sorting comparator

   The comparator returns true if a.profit < b.profit, which sorts ascending by profit.

2. Step 2: Understand scheduling logic

   Jobs must be sorted descending by profit to schedule highest profit jobs first.

3. Final Answer:

   Sorting comparator sorts ascending instead of descending -> Option A

4. Quick Check:

   Comparator must sort descending [OK]

Hint: Sort jobs descending by profit for correct scheduling [OK]

Common Mistakes:

• Using ascending sort comparator
• Incorrect slot vector size off by one
• Loop direction confusion

5. You have 6 jobs with deadlines and profits:
jobs = [{id:1, d:4, p:70}, {id:2, d:1, p:80}, {id:3, d:1, p:30}, {id:4, d:1, p:100}, {id:5, d:3, p:40}, {id:6, d:2, p:20}]
Using the job scheduling algorithm, what is the maximum profit and which jobs are scheduled?

hard

A. Profit: 230; Jobs scheduled: 4 -> 1 -> 5 -> 6

B. Profit: 220; Jobs scheduled: 4 -> 2 -> 5 -> 6

C. Profit: 240; Jobs scheduled: 4 -> 2 -> 1 -> 5

D. Profit: 210; Jobs scheduled: 4 -> 1 -> 3 -> 5

Solution

1. Step 1: Sort jobs by profit descending

   Sorted: (4,100,1), (2,80,1), (1,70,4), (5,40,3), (3,30,1), (6,20,2)

2. Step 2: Schedule jobs greedily before deadlines

   Schedule job 4 at slot 1 (deadline 1), job 6 at slot 2 (deadline 2), job 5 at slot 3 (deadline 3), job 1 at slot 4 (deadline 4). Jobs 2 and 3 cannot fit because slot 1 is taken by job 4.

3. Step 3: Calculate total profit and jobs scheduled

   Profit = 100 + 20 + 40 + 70 = 230; Scheduled jobs in order of slots: 4 -> 6 -> 5 -> 1 (slots 1,2,3,4)

4. Final Answer:

   Profit: 230; Jobs scheduled: 4 -> 6 -> 5 -> 1 -> Option A

5. Quick Check:

   Max profit = 230 with jobs 4,6,5,1 [OK]

Hint: Sort by profit, assign latest free slot before deadline [OK]

Common Mistakes:

• Scheduling multiple jobs in same slot
• Ignoring deadlines when scheduling
• Not sorting jobs by profit first