Job Scheduling with Deadlines in DSA C#

Mental Model

We want to do as many jobs as possible before their deadlines to get the highest total profit. We pick jobs that finish on time and give the most money.

Analogy: Imagine you have a list of tasks to do before certain times, and each task pays differently. You want to pick tasks that fit in your schedule and pay the most, like choosing appointments that don't overlap and pay well.

Jobs: [Job1(profit=20, deadline=2)] -> [Job2(profit=15, deadline=2)] -> [Job3(profit=10, deadline=1)] -> null
Schedule slots: [1] [2] [3] ... (each slot can hold one job before its deadline)

Dry Run Walkthrough

Input: Jobs: [(profit=20, deadline=2), (profit=15, deadline=2), (profit=10, deadline=1), (profit=5, deadline=3)]

Goal: Schedule jobs to maximize total profit without missing deadlines

Step 1: Sort jobs by profit descending

Jobs sorted: [(20,2), (15,2), (10,1), (5,3)]

Why: We want to try scheduling the most profitable jobs first

Step 2: Schedule job with profit 20 and deadline 2 in slot 2

Schedule: [empty, Job(20,2), empty]

Why: Place job in latest available slot before deadline

Step 3: Schedule job with profit 15 and deadline 2 in slot 1

Schedule: [Job(15,2), Job(20,2), empty]

Why: Slot 2 is taken, so use earlier slot 1

Step 4: Try to schedule job with profit 10 and deadline 1 but slot 1 is taken, so skip

Schedule unchanged: [Job(15,2), Job(20,2), empty]

Why: No free slot before deadline 1

Step 5: Schedule job with profit 5 and deadline 3 in slot 3

Schedule: [Job(15,2), Job(20,2), Job(5,3)]

Why: Slot 3 is free and before deadline 3

Result:

Schedule: [Job(15,2)] -> [Job(20,2)] -> [Job(5,3)] -> null
Total profit: 40

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Job
{
    public int Profit { get; set; }
    public int Deadline { get; set; }
    public Job(int profit, int deadline)
    {
        Profit = profit;
        Deadline = deadline;
    }
}

class JobScheduling
{
    public static int ScheduleJobs(List<Job> jobs)
    {
        // Sort jobs by profit descending
        jobs.Sort((a, b) => b.Profit.CompareTo(a.Profit));

        int maxDeadline = 0;
        foreach (var job in jobs)
            if (job.Deadline > maxDeadline) maxDeadline = job.Deadline;

        // Initialize schedule slots, 1-based indexing for convenience
        Job[] schedule = new Job[maxDeadline + 1];

        int totalProfit = 0;

        foreach (var job in jobs)
        {
            // Try to schedule job in latest free slot before deadline
            for (int slot = job.Deadline; slot > 0; slot--)
            {
                if (schedule[slot] == null)
                {
                    schedule[slot] = job; // assign job to slot
                    totalProfit += job.Profit; // add profit
                    break; // move to next job
                }
            }
        }

        // Print scheduled jobs in order
        for (int i = 1; i <= maxDeadline; i++)
        {
            if (schedule[i] != null)
                Console.WriteLine($"Slot {i}: Job with profit {schedule[i].Profit} and deadline {schedule[i].Deadline}");
            else
                Console.WriteLine($"Slot {i}: Empty");
        }

        Console.WriteLine($"Total profit: {totalProfit}");
        return totalProfit;
    }

    static void Main()
    {
        var jobs = new List<Job>
        {
            new Job(20, 2),
            new Job(15, 2),
            new Job(10, 1),
            new Job(5, 3)
        };

        ScheduleJobs(jobs);
    }
}

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

Sort jobs by profit descending to prioritize high profit jobs

foreach (var job in jobs) if (job.Deadline > maxDeadline) maxDeadline = job.Deadline;

Find maximum deadline to size schedule array

Job[] schedule = new Job[maxDeadline + 1];

Create schedule slots array indexed by time slot

for (int slot = job.Deadline; slot > 0; slot--)

Try to find latest free slot before job deadline

if (schedule[slot] == null) { schedule[slot] = job; totalProfit += job.Profit; break; }

Assign job to free slot and add profit, then stop searching

Output

Slot 1: Job with profit 15 and deadline 2

Slot 2: Job with profit 20 and deadline 2

Slot 3: Job with profit 5 and deadline 3

Total profit: 40

Complexity Analysis

Time: O(n log n) because we sort the jobs by profit and then for each job we try to find a free slot up to its deadline

Space: O(n) for the schedule array and job list storage

vs Alternative: Compared to trying all permutations (O(n!)), this greedy approach is much faster and practical

Edge Cases

No jobs

Returns total profit 0 and prints no scheduled jobs

DSA C#

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

All jobs have the same deadline

Schedules the most profitable jobs up to the number of slots available

DSA C#

for (int slot = job.Deadline; slot > 0; slot--)

Jobs with deadlines greater than number of jobs

Schedules jobs only up to max deadline slots, ignoring extra deadline slots

DSA C#

int maxDeadline = 0; foreach (var job in jobs) if (job.Deadline > maxDeadline) maxDeadline = job.Deadline;

When to Use This Pattern

When you see tasks with deadlines and profits and need to maximize profit by scheduling without overlap, use the greedy job scheduling pattern to assign jobs starting from the most profitable.

Common Mistakes

Mistake: Scheduling jobs in order of deadline instead of profit
Fix: Sort jobs by profit descending before scheduling

Mistake: Assigning jobs to earliest free slot instead of latest before deadline
Fix: Try slots from job deadline backward to find latest free slot

Summary

Schedules jobs to maximize total profit without missing deadlines.

Use when you have jobs with deadlines and profits and want to maximize earnings.

Sort jobs by profit and assign each to the latest free slot before its deadline.

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