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 job 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#

class Job {
  public int id, deadline, profit;
}

// Sort jobs by profit
// Assign jobs to slots before deadline
// Print scheduled jobs and profit

Schedules jobs with deadlines to maximize profit by placing highest profit jobs first in available slots.

Execution Table

Step	Current Job (id, deadline, profit)	Action	Slot Checked	Slot Assigned	Schedule State	Total Profit
1	(4, 2, 100)	Check slot 2	2	2	[_, 4, _, _]	100
2	(2, 1, 80)	Check slot 1	1	1	[2, 4, _, _]	180
3	(1, 4, 70)	Check slot 4	4	4	[2, 4, _, 1]	250
4	(5, 3, 40)	Check slot 3	3	3	[2, 4, 5, 1]	290
5	(3, 1, 30)	Check slot 1 (occupied), no slot	1	None	[2, 4, 5, 1]	290
6	End of jobs	-	-	-	[2, 4, 5, 1]	290

💡 All jobs processed or no slots available before deadlines

Variable Tracker

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

Key Moments - 2 Insights

Why do we check the latest slot before the job's deadline instead of the earliest?

Checking the latest slot before the deadline (see execution_table rows 1,2,3,4) allows earlier slots to remain free for other jobs with earlier deadlines, maximizing total scheduled jobs and profit.

What happens if a slot is already occupied when trying to schedule a job?

If the slot is occupied (row 5), we try earlier slots before the deadline. If none are free, the job is skipped to avoid conflicts, as shown in execution_table row 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 2. Which slot was assigned to job 2?

A Slot 1

B Slot 2

C Slot 3

D Slot 4

💡 Hint

Check the 'Slot Assigned' column in execution_table row 2.

At which step does the total profit first reach 250?

A Step 4

B Step 5

C Step 3

D Step 6

💡 Hint

Look at the 'Total Profit' column in execution_table rows 3 and 4.

If job 3 had a deadline of 2 instead of 1, what would happen in the schedule?

A Job 3 would be scheduled at slot 3

B Job 3 would not be scheduled

C Job 3 would be scheduled at slot 2

D Job 3 would replace job 4

💡 Hint

Refer to how slots are checked from latest to earliest before deadline in execution_table.

Concept Snapshot

Job Scheduling with Deadlines:
- Sort jobs by profit descending
- For each job, assign to latest free slot before deadline
- Skip if no slot available
- Maximizes total profit
- Schedule stored as array of slots

Full Transcript

Job Scheduling with Deadlines arranges jobs to maximize profit by sorting them by profit and placing each job in the latest available slot before its deadline. The process starts with an empty schedule. Each job is checked in order, and the latest free slot before its deadline is assigned. If no slot is free, the job is skipped. This ensures maximum profit without overlapping jobs. The schedule and total profit update step-by-step as jobs are assigned or skipped.

Practice

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

easy

A. Maximize total profit by scheduling jobs before their deadlines

B. Minimize the number of jobs scheduled

C. Schedule jobs in the order they arrive without considering deadlines

D. Maximize the number of jobs scheduled regardless of profit

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Identify the optimization criteria

   We want to maximize the total profit earned by scheduling jobs within their deadlines.

3. Final Answer:

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

4. Quick Check:

   Goal = Maximize profit [OK]

Hint: Focus on profit maximization within deadlines [OK]

Common Mistakes:

• Thinking the goal is to schedule all jobs regardless of profit
• Ignoring deadlines when scheduling
• Assuming jobs must be scheduled in input order

2. Which of the following C# code snippets correctly sorts an array of jobs by their profit in descending order?

easy

A. Array.Sort(jobs, (a, b) => a.Profit.CompareTo(b.Profit));

B. Array.Sort(jobs, (a, b) => b.Profit.CompareTo(a.Profit));

C. jobs.OrderBy(job => job.Profit);

D. jobs.OrderByDescending(job => job.Deadline);

Solution

1. Step 1: Identify sorting by profit descending

   Sorting by profit descending means higher profit first, so compare b.Profit to a.Profit.

2. Step 2: Check C# syntax for Array.Sort with custom comparer

   Array.Sort with lambda (a, b) => b.Profit.CompareTo(a.Profit) sorts descending by profit.

3. Final Answer:

   Array.Sort(jobs, (a, b) => b.Profit.CompareTo(a.Profit)); -> Option B

4. Quick Check:

   Descending profit sort = Array.Sort(jobs, (a, b) => b.Profit.CompareTo(a.Profit)); [OK]

Hint: Use b.CompareTo(a) for descending order in C# [OK]

Common Mistakes:

• Using a.Profit.CompareTo(b.Profit) which sorts ascending
• Using OrderBy instead of OrderByDescending for descending
• Sorting by deadline instead of profit

3. Given the following jobs with (JobId, Deadline, Profit): (1, 2, 100), (2, 1, 19), (3, 2, 27), (4, 1, 25), (5, 3, 15), what is the maximum profit achievable by scheduling jobs before their deadlines?

medium

A. 127

B. 115

C. 142

D. 100

Solution

1. Step 1: Sort jobs by profit descending

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

2. Step 2: Schedule jobs greedily before deadlines

   Schedule Job 1 at slot 2, Job 3 at slot 1 (since slot 2 taken), Job 5 at slot 3. Jobs 4 and 2 cannot be scheduled as slots 1 and 2 are taken.

3. Step 3: Calculate total profit

   Profit = 100 + 27 + 15 = 142

4. Final Answer:

   142 -> Option C

5. Quick Check:

   Max profit = 142 [OK]

Hint: Schedule highest profit jobs first in latest free slot [OK]

Common Mistakes:

• Scheduling jobs without sorting by profit
• Assigning jobs to earliest slots instead of latest free slot
• Counting jobs that miss deadlines

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

Array.Sort(jobs, (a, b) => a.Profit.CompareTo(b.Profit));
foreach (var job in jobs) {
  for (int slot = job.Deadline; slot > 0; slot--) {
    if (timeSlots[slot] == false) {
      timeSlots[slot] = true;
      totalProfit += job.Profit;
      break;
    }
  }
}

medium

A. totalProfit should be incremented outside the loop

B. Loop should start from slot = 1 to deadline, not reverse

C. timeSlots array indexing is off by one

D. Jobs are sorted in ascending profit order, should be descending

Solution

1. Step 1: Check sorting order

   Sorting by a.Profit.CompareTo(b.Profit) sorts ascending, but we need descending to maximize profit.

2. Step 2: Verify scheduling logic

   The loop tries to assign job to latest free slot before deadline, which is correct.

3. Final Answer:

   Jobs are sorted in ascending profit order, should be descending -> Option D

4. Quick Check:

   Sort descending by profit [OK]

Hint: Sort jobs by descending profit to maximize total profit [OK]

Common Mistakes:

• Sorting ascending profit by mistake
• Incorrect slot iteration direction
• Misindexing timeSlots array

5. You have 4 jobs with (JobId, Deadline, Profit): (1, 4, 20), (2, 1, 10), (3, 1, 40), (4, 1, 30). Using the job scheduling algorithm, which jobs will be scheduled and what is the total profit?

hard

A. Jobs: 3, 1; Total Profit: 60

B. Jobs: 3, 4, 1; Total Profit: 90

C. Jobs: 1, 2; Total Profit: 30

D. Jobs: 4, 1; Total Profit: 50

Solution

1. Step 1: Sort jobs by profit descending

   Sorted: (3,1,40), (4,1,30), (1,4,20), (2,1,10)

2. Step 2: Schedule jobs in latest free slot before deadline

   Job 3 scheduled at slot 1, Job 4 cannot be scheduled (slot 1 taken), Job 1 scheduled at slot 4, Job 2 cannot be scheduled (slot 1 taken)

3. Step 3: Calculate total profit

   Total profit = 40 + 20 = 60

4. Final Answer:

   Jobs: 3, 1; Total Profit: 60 -> Option A

5. Quick Check:

   Schedule highest profit jobs first [OK]

Hint: Schedule highest profit jobs first in latest free slot [OK]

Common Mistakes:

• Trying to schedule all jobs ignoring slot availability
• Scheduling jobs in input order
• Not checking slot availability correctly