Job Scheduling with Deadlines in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort jobs by their deadlines in ascending order.

DSA C#

jobs.Sort((a, b) => a.[1].CompareTo(b.Deadline));

Drag options to blanks, or click blank then click option'

ADeadline

BProfit

CId

DDuration

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting by Profit instead of Deadline.

Using wrong property names.

Sorting in descending order.

Sorting jobs by their Deadline helps us schedule jobs before their deadlines.

2fill in blank

medium

Complete the code to check if a time slot is free before scheduling a job.

DSA C#

if (slots[[1]] == false) { /* schedule job */ }

Drag options to blanks, or click blank then click option'

Ajob.Deadline

Bi

Ctime

Djob.Profit

Attempts:

3 left

💡 Hint

Common Mistakes

Using job.Deadline as index directly.

Checking wrong array or variable.

Using profit as index.

We check the slot at index i to see if it is free (false) before scheduling.

3fill in blank

hard

Fix the error in the loop that tries to find a free slot for a job before its deadline.

DSA C#

for (int i = Math.Min(maxDeadline, job.Deadline); i > 0; i[1]) { /* check slot */ }

Drag options to blanks, or click blank then click option'

A+=

B++

C-=

D--

Attempts:

3 left

💡 Hint

Common Mistakes

Using ++ causes infinite loop or wrong slot checking order.

Using += or -= with wrong values.

Not decrementing i.

We decrement i to check slots from the job's deadline backwards to find a free slot.

4fill in blank

hard

Fill both blanks to correctly mark a slot as occupied and add the job's profit.

DSA C#

slots[[1]] = true;
totalProfit [2]= job.Profit;

Drag options to blanks, or click blank then click option'

Ai

B+

C-

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong slot index variable.

Using '-' instead of '+=' for profit.

Marking slot as false instead of true.

Marking slot i as true means it's occupied, and adding job.Profit to totalProfit accumulates profit.

5fill in blank

hard

Fill all three blanks to create a dictionary of scheduled jobs with their profits, filtering only profitable jobs.

DSA C#

var scheduledJobs = jobs.Where(job => job.Profit [1] 0)
    .ToDictionary(job => job.[2], job => job.[3]);

Drag options to blanks, or click blank then click option'

A>

BId

CProfit

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' instead of '>' in filter.

Using wrong properties for dictionary keys or values.

Not filtering profitable jobs.

We filter jobs with Profit > 0, then create a dictionary with job Id as key and Profit as value.

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