Job Scheduling with Deadlines in DSA C# - Build from Scratch

Job Scheduling with Deadlines

📖 Scenario: You are managing a small workshop where you have several jobs to complete. Each job has a deadline and a profit if completed on time. You want to schedule the jobs to maximize your total profit without missing any deadlines.

🎯 Goal: Build a program that schedules jobs with deadlines to maximize total profit. You will create the job list, set the maximum deadline, select jobs to maximize profit, and print the scheduled jobs.

📋 What You'll Learn

Create a list of jobs with exact given properties

Set a maximum deadline variable

Implement the job scheduling logic to maximize profit

Print the scheduled jobs in order

💡 Why This Matters

🌍 Real World

Job scheduling is used in manufacturing, computer task scheduling, and project management to maximize resource use and profit.

💼 Career

Understanding job scheduling algorithms helps in roles like software development, operations management, and systems engineering.

1

Create the list of jobs

Create a list called jobs of type List<Job> with these exact jobs: Job('a', 2, 100), Job('b', 1, 19), Job('c', 2, 27), Job('d', 1, 25), Job('e', 3, 15). Define the Job class with public fields id (char), deadline (int), and profit (int).

DSA C#

// Define the Job class and create the jobs list
// Your code here

Hint

Define the Job class first with the required fields and constructor. Then create the jobs list with the exact jobs.

2

Set the maximum deadline

Create an integer variable called maxDeadline and set it to 3.

DSA C#

using System;
using System.Collections.Generic;

public class Job
{
    public char id;
    public int deadline;
    public int profit;

    public Job(char id, int deadline, int profit)
    {
        this.id = id;
        this.deadline = deadline;
        this.profit = profit;
    }
}

class Program
{
    static void Main()
    {
        List jobs = new List
        {
            new Job('a', 2, 100),
            new Job('b', 1, 19),
            new Job('c', 2, 27),
            new Job('d', 1, 25),
            new Job('e', 3, 15)
        };
        // Create maxDeadline variable and set to 3
        // Your code here
    }
}

Hint

Just create an integer variable named maxDeadline and assign it the value 3.

3

Implement job scheduling logic

Sort the jobs list in descending order by profit. Create a boolean array called slots of size maxDeadline initialized to false. Create a list called result to store scheduled jobs. Use a for loop with variable i to iterate over jobs. Inside, use a for loop with variable j from Math.Min(maxDeadline, jobs[i].deadline) - 1 down to 0. If slots[j] is false, assign true to slots[j], add jobs[i] to result, and break the inner loop.

DSA C#

using System;
using System.Collections.Generic;

public class Job
{
    public char id;
    public int deadline;
    public int profit;

    public Job(char id, int deadline, int profit)
    {
        this.id = id;
        this.deadline = deadline;
        this.profit = profit;
    }
}

class Program
{
    static void Main()
    {
        List jobs = new List
        {
            new Job('a', 2, 100),
            new Job('b', 1, 19),
            new Job('c', 2, 27),
            new Job('d', 1, 25),
            new Job('e', 3, 15)
        };
        int maxDeadline = 3;
        // Sort jobs by profit descending
        // Create slots array
        // Create result list
        // Schedule jobs using nested loops
        // Your code here
    }
}

Hint

Sort jobs by profit descending. Use a boolean array to track free slots. Loop over jobs and try to place each job in the latest free slot before its deadline.

4

Print the scheduled jobs

Use a foreach loop with variable job to iterate over result. Inside the loop, print the job id using Console.Write(job.id + " ").

DSA C#

using System;
using System.Collections.Generic;

public class Job
{
    public char id;
    public int deadline;
    public int profit;

    public Job(char id, int deadline, int profit)
    {
        this.id = id;
        this.deadline = deadline;
        this.profit = profit;
    }
}

class Program
{
    static void Main()
    {
        List jobs = new List
        {
            new Job('a', 2, 100),
            new Job('b', 1, 19),
            new Job('c', 2, 27),
            new Job('d', 1, 25),
            new Job('e', 3, 15)
        };
        int maxDeadline = 3;

        jobs.Sort((x, y) => y.profit.CompareTo(x.profit));

        bool[] slots = new bool[maxDeadline];
        List result = new List();

        for (int i = 0; i = 0; j--)
            {
                if (!slots[j])
                {
                    slots[j] = true;
                    result.Add(jobs[i]);
                    break;
                }
            }
        }
        // Print scheduled jobs
        // Your code here
    }
}

Hint

Loop over the result list and print each job's id followed by a space.

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