Job Scheduling with Deadlines in DSA C++ - Execution Trace

Concept Flow - Job Scheduling with Deadlines

Start with list of jobs

↓

Sort jobs by profit descending

↓

Initialize schedule slots as empty

↓

For each job in sorted list

↓

Find latest free slot before deadline

↓

If slot found, assign job to slot

↓

Repeat for all jobs

↓

Output scheduled jobs and total profit

Sort jobs by profit, then assign each to the latest free slot before its deadline to maximize total profit.

Execution Sample

DSA C++

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

// Sort jobs by profit descending
// Assign jobs to latest free slot before deadline
// Print scheduled jobs and total profit

This code schedules jobs to maximize profit by placing each job in the latest available slot before its deadline.

Execution Table

Step	Job Considered (id, deadline, profit)	Slot Checked	Slot Status	Action	Scheduled Slots	Total Profit
1	(4, 2, 100)	2	Empty	Assign job 4 to slot 2	[_, 4, _, _]	100
2	(2, 1, 80)	1	Empty	Assign job 2 to slot 1	[2, 4, _, _]	180
3	(1, 4, 70)	4	Empty	Assign job 1 to slot 4	[2, 4, _, 1]	250
4	(5, 3, 40)	3	Empty	Assign job 5 to slot 3	[2, 4, 5, 1]	290
5	(3, 1, 30)	1	Occupied	No slot available, skip job 3	[2, 4, 5, 1]	290
6	All jobs considered	-	-	Scheduling complete	[2, 4, 5, 1]	290

💡 All jobs processed or no free slots available for remaining jobs

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
scheduled_slots	[_, _, _, _]	[_, 4, _, _]	[2, 4, _, _]	[2, 4, _, 1]	[2, 4, 5, 1]	[2, 4, 5, 1]	[2, 4, 5, 1]
total_profit	0	100	180	250	290	290	290

Key Moments - 3 Insights

Why do we assign job 1 to slot 4 instead of an earlier slot?

Because job 1's deadline is 4, we try to assign it to the latest free slot before or on deadline 4. Slot 4 is free, so we assign it there to keep earlier slots free for other jobs (see execution_table step 3).

Why is job 3 skipped even though it has a deadline of 1?

At step 5, slot 1 is already occupied by job 2, and no earlier slots exist. So job 3 cannot be scheduled (execution_table step 5).

How does sorting jobs by profit help in scheduling?

Sorting ensures we try to schedule the most profitable jobs first, maximizing total profit by filling slots with high-profit jobs before lower-profit ones.

Visual Quiz - 3 Questions

Look at the execution_table, what is the total profit after scheduling job 1?

A 150

B 250

C 290

D 70

💡 Hint

Check the 'Total Profit' column at step 3 in execution_table

At which step does the algorithm skip a job because no slot is free?

A Step 5

B Step 2

C Step 3

D Step 1

💡 Hint

Look for 'No slot available' action in execution_table

If job 5 had a deadline of 2 instead of 3, what would happen at step 4?

A Job 5 assigned to slot 3

B Job 5 assigned to slot 2

C Job 5 skipped due to no free slot

D Job 5 assigned to slot 1

💡 Hint

Check slot availability before deadline 2 at step 4 in variable_tracker and execution_table

Concept Snapshot

Job Scheduling with Deadlines:
- Sort jobs by profit descending
- For each job, assign to latest free slot before deadline
- If no slot free, skip job
- Maximizes total profit
- Slots represent time units
- Output scheduled jobs and total profit

Full Transcript

Job Scheduling with Deadlines is a method to maximize profit by scheduling jobs within their deadlines. We start with a list of jobs, each having an id, deadline, and profit. First, we sort jobs by profit from highest to lowest. Then, for each job, we try to assign it to the latest free time slot before or on its deadline. If the slot is free, we assign the job there; if not, we check earlier slots. If no slot is free, we skip that job. This way, we fill the schedule with the most profitable jobs possible. The execution table shows each step: which job is considered, which slot is checked, and the action taken. The variable tracker shows how scheduled slots and total profit change after each step. Key moments clarify why we assign jobs to latest slots and why some jobs get skipped. The visual quiz tests understanding of total profit updates, skipped jobs, and slot assignments. This approach ensures maximum profit by smartly placing jobs within their deadlines.

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