Job Scheduling with Deadlines in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Job Scheduling Maximum Profit

What is the output of the following C++ code that schedules jobs to maximize profit given deadlines?

DSA C++

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

struct Job {
    char id;
    int deadline;
    int profit;
};

bool cmp(Job a, Job b) {
    return a.profit > b.profit;
}

int main() {
    vector<Job> jobs = {{'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27}, {'d', 1, 25}, {'e', 3, 15}};
    sort(jobs.begin(), jobs.end(), cmp);
    int n = jobs.size();
    vector<int> result(n, -1);
    vector<bool> slot(n, false);

    for (int i = 0; i < n; i++) {
        for (int j = min(n, jobs[i].deadline) - 1; j >= 0; j--) {
            if (!slot[j]) {
                slot[j] = true;
                result[j] = i;
                break;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (result[i] != -1) {
            cout << jobs[result[i]].id << " ";
        }
    }
    return 0;
}

A a d c

B a c e

C c a e

D b d e

💡 Hint

Sort jobs by profit descending and assign each job to the latest available slot before its deadline.

Jobs are sorted by profit: a(100), c(27), d(25), b(19), e(15). Assign 'a' to slot 1 (deadline 2), 'c' to slot 0 (deadline 2), and 'e' to slot 2 (deadline 3). Output is 'a c e'.

🧠 Conceptual

intermediate

Maximum Number of Jobs Scheduled

Given 5 jobs with deadlines and profits, what is the maximum number of jobs that can be scheduled without overlapping deadlines?

A 3

B 2

C 5

D 4

💡 Hint

Each job takes 1 unit time and must be completed before its deadline.

The maximum number of jobs scheduled equals the number of available slots before deadlines. For the given jobs, 3 jobs can be scheduled without conflict.

🔧 Debug

advanced

Identify the Bug in Job Scheduling Code

What error will the following code produce when run?

DSA C++

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

struct Job {
    char id;
    int deadline;
    int profit;
};

bool cmp(Job a, Job b) {
    return a.profit < b.profit;
}

int main() {
    vector<Job> jobs = {{'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27}};
    sort(jobs.begin(), jobs.end(), cmp);
    int n = jobs.size();
    vector<int> result(n, -1);
    vector<bool> slot(n, false);

    for (int i = 0; i < n; i++) {
        for (int j = min(n, jobs[i].deadline) - 1; j >= 0; j--) {
            if (!slot[j]) {
                slot[j] = true;
                result[j] = i;
                break;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (result[i] != -1) {
            cout << jobs[result[i]].id << " ";
        }
    }
    return 0;
}

A Compilation error due to comparator

B Outputs jobs in descending profit order

C Runtime error due to invalid index

D Outputs jobs in ascending profit order

💡 Hint

Check the comparator function used in sort.

The comparator sorts jobs by profit ascending (lowest first), so the scheduling picks lower profit jobs first, resulting in output in ascending profit order.

🚀 Application

advanced

Calculate Total Profit from Scheduled Jobs

Given jobs with deadlines and profits, what is the total profit after scheduling optimally?

DSA C++

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

struct Job {
    char id;
    int deadline;
    int profit;
};

bool cmp(Job a, Job b) {
    return a.profit > b.profit;
}

int main() {
    vector<Job> jobs = {{'a', 4, 70}, {'b', 1, 80}, {'c', 1, 30}, {'d', 1, 100}, {'e', 3, 40}, {'f', 2, 20}};
    sort(jobs.begin(), jobs.end(), cmp);
    int n = jobs.size();
    vector<int> result(n, -1);
    vector<bool> slot(n, false);
    int total_profit = 0;

    for (int i = 0; i < n; i++) {
        for (int j = min(n, jobs[i].deadline) - 1; j >= 0; j--) {
            if (!slot[j]) {
                slot[j] = true;
                result[j] = i;
                total_profit += jobs[i].profit;
                break;
            }
        }
    }

    cout << total_profit;
    return 0;
}

A 230

B 240

C 310

D 260

💡 Hint

Schedule jobs by descending profit and assign to latest free slot before deadline, summing profits.

Scheduled jobs: d(100) slot 0, a(70) slot 3, e(40) slot 2, f(20) slot 1. Total profit = 100+70+40+20=230. Jobs b and c cannot be scheduled due to slot conflicts.

🧠 Conceptual

expert

Why Greedy Algorithm Works for Job Scheduling with Deadlines

Why does the greedy approach of sorting jobs by profit and assigning each to the latest free slot before its deadline produce an optimal solution?

A Because it always schedules the job with the earliest deadline first

B Because it schedules jobs in the order they appear in the input list

C Because it maximizes profit locally at each step ensuring global maximum profit

D Because it minimizes the number of scheduled jobs

💡 Hint

Think about how local choices affect the overall profit.

The greedy method picks the highest profit job first and places it in the latest possible slot before its deadline, ensuring no higher profit job is displaced. This local optimization leads to a global maximum profit.

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