Job Scheduling with Deadlines in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

To schedule jobs so that the maximum number of jobs are completed before their deadlines, maximizing total profit or count.

beginner

In Job Scheduling with Deadlines, why do we sort jobs by profit or deadline?

Sorting jobs by profit helps prioritize high-profit jobs first, while sorting by deadline helps schedule jobs within their allowed time frames.

intermediate

What data structure is commonly used to keep track of free time slots in Job Scheduling with Deadlines?

An array or disjoint set (union-find) structure is used to efficiently find and assign free time slots for jobs.

intermediate

Explain the greedy approach used in Job Scheduling with Deadlines.

Sort jobs by descending profit, then for each job, assign it to the latest available slot before its deadline to maximize profit.

beginner

What happens if a job cannot be scheduled before its deadline in Job Scheduling with Deadlines?

The job is skipped because scheduling it would miss the deadline and reduce overall profit or count.

What is the first step in the greedy algorithm for Job Scheduling with Deadlines?

A Sort jobs by descending profit

B Sort jobs by ascending deadline

C Schedule jobs randomly

D Assign jobs to earliest slots

Sorting jobs by descending profit ensures we consider the most valuable jobs first.

If a job has a deadline of 3, which time slots can it be scheduled in?

A Only slot 3

B Any slot before or at 3

C Any slot after 3

D Only slot 1

Jobs must be scheduled before or on their deadline to be valid.

What is the main reason to skip a job during scheduling?

A It is the longest job

B It has the lowest profit

C It has the earliest deadline

D No free slot before its deadline

If no free slot is available before the job's deadline, it cannot be scheduled.

Which data structure helps find the latest free slot efficiently?

A Disjoint set (union-find)

B Queue

C Stack

D Linked list

Disjoint set helps quickly find and merge free slots.

What does the Job Scheduling with Deadlines problem maximize?

A Total number of jobs scheduled

B Total time spent

C Total profit from scheduled jobs

D Number of missed deadlines

The goal is to maximize total profit by scheduling jobs before deadlines.

Describe the greedy strategy used to solve the Job Scheduling with Deadlines problem.

Think about how to pick jobs and where to place them.

Explain how to efficiently find a free time slot for a job before its deadline.

Consider data structures that help track free slots.

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