Job Scheduling with Deadlines in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Job Scheduling Result

What is the output of the following C# code that schedules jobs with deadlines and profits?

DSA C#

using System;
using System.Collections.Generic;

class Job {
    public char Id;
    public int Deadline;
    public int Profit;
    public Job(char id, int deadline, int profit) {
        Id = id;
        Deadline = deadline;
        Profit = profit;
    }
}

class Program {
    static void Main() {
        List<Job> jobs = new List<Job> {
            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)
        };

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

        int n = jobs.Count;
        char[] result = new char[n];
        bool[] slot = new bool[n];

        for (int i = 0; i < n; i++) {
            for (int j = Math.Min(n, jobs[i].Deadline) - 1; j >= 0; j--) {
                if (!slot[j]) {
                    slot[j] = true;
                    result[j] = jobs[i].Id;
                    break;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (slot[i])
                Console.Write(result[i] + " ");
        }
    }

A a b c

B a d e

C b d e

D c a e

💡 Hint

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

The code sorts jobs by profit descending: a(100), c(27), d(25), b(19), e(15).

It tries to schedule each job in the latest available slot before its deadline.

Slots: 0,1,2 (3 slots for 3 max deadline).

Job 'a' (deadline 2) goes to slot 1.

Job 'c' (deadline 2) goes to slot 0.

Job 'd' (deadline 1) cannot fit (slot 0 taken), skipped.

Job 'b' (deadline 1) cannot fit, skipped.

Job 'e' (deadline 3) goes to slot 2.

Output is 'c a e '.

🧠 Conceptual

intermediate

Maximum Number of Jobs Scheduled

Given 5 jobs with deadlines and profits, what is the maximum number of jobs that can be scheduled without overlapping deadlines?

DSA C#

Jobs:
Job A: deadline=2, profit=100
Job B: deadline=1, profit=19
Job C: deadline=2, profit=27
Job D: deadline=1, profit=25
Job E: deadline=3, profit=15

A 2

B 3

C 4

D 5

💡 Hint

Maximum jobs scheduled equals the number of available slots before deadlines.

The maximum deadline is 3, so at most 3 jobs can be scheduled.

By scheduling jobs greedily by profit, 3 jobs fit without deadline conflicts.

🔧 Debug

advanced

Identify the Error in Job Scheduling Code

What error will the following C# code produce when run?

DSA C#

using System;
using System.Collections.Generic;

class Job {
    public char Id;
    public int Deadline;
    public int Profit;
    public Job(char id, int deadline, int profit) {
        Id = id;
        Deadline = deadline;
        Profit = profit;
    }
}

class Program {
    static void Main() {
        List<Job> jobs = new List<Job> {
            new Job('a', 2, 100),
            new Job('b', 1, 19),
            new Job('c', 3, 27)
        };

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

        int n = jobs.Count;
        char[] result = new char[n];
        bool[] slot = new bool[n];

        for (int i = 0; i < n; i++) {
            for (int j = jobs[i].Deadline; j >= 0; j--) {
                if (!slot[j]) {
                    slot[j] = true;
                    result[j] = jobs[i].Id;
                    break;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (slot[i])
                Console.Write(result[i] + " ");
        }
    }

A IndexOutOfRangeException

B NullReferenceException

C No error, outputs 'a c b '

D Compile-time error

💡 Hint

Check the inner loop index range and array access.

The inner loop starts at jobs[i].Deadline which can be equal to n (array length), causing index out of range when accessing slot[j].

Array indices go from 0 to n-1, so j should start at Math.Min(n, jobs[i].Deadline) - 1.

📝 Syntax

advanced

Correct the Syntax Error in Job Scheduling Code

Which option fixes the syntax error in this C# code snippet for job scheduling?

DSA C#

var jobs = new List<Job> {
    new Job('a', 2, 100),
    new Job('b', 1, 19),
    new Job('c', 2, 27)
};

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

int n = jobs.Count;
char[] result = new char[n];
bool[] slot = new bool[n];

for (int i = 0; i < n; i++) {
    for (int j = Math.Min(n, jobs[i].Deadline) - 1; j >= 0; j--) {
        if (!slot[j]) {
            slot[j] = true;
            result[j] = jobs[i].Id;
            break;
        }
    }

A Add semicolon after result[j] = jobs[i].Id

B Change 'var jobs' to 'List<Job> jobs'

C Replace 'Math.Min' with 'Math.max'

D Remove 'break;' statement

💡 Hint

Check line endings for missing semicolons.

The line 'result[j] = jobs[i].Id' is missing a semicolon at the end, causing a syntax error.

Adding the semicolon fixes the syntax error.

🚀 Application

expert

Calculate Maximum Profit from Job Scheduling

Given the following jobs with deadlines and profits, what is the maximum total profit achievable by scheduling jobs without overlapping deadlines?

DSA C#

Jobs:
Job A: deadline=4, profit=70
Job B: deadline=1, profit=80
Job C: deadline=1, profit=30
Job D: deadline=2, profit=100
Job E: deadline=3, profit=40
Job F: deadline=2, profit=20

A 220

B 240

C 290

D 210

💡 Hint

Schedule jobs by descending profit and assign to latest free slot before deadline.

Sort jobs by profit descending: D(100), B(80), A(70), E(40), C(30), F(20).

Schedule D at slot 1 (deadline 2), B at slot 0 (deadline 1), A at slot 3 (deadline 4), E at slot 2 (deadline 3).

Jobs C and F cannot be scheduled due to slot conflicts.

Total profit = 100 + 80 + 70 + 40 = 290.

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