Job Scheduling with Deadlines in DSA C

Mental Model

We want to schedule jobs so that we finish as many as possible before their deadlines, choosing the most profitable ones first.

Analogy: Imagine you have several tasks to do before certain times, but you only have limited hours. You pick the most rewarding tasks that fit your schedule first.

Jobs: [Job1: profit=20, deadline=2]
      [Job2: profit=15, deadline=2]
      [Job3: profit=10, deadline=1]
      [Job4: profit=5, deadline=3]
      [Job5: profit=1, deadline=3]
Slots: 1 -> 2 -> 3 -> null (time slots available)

Dry Run Walkthrough

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

Goal: Schedule jobs to maximize total profit without missing deadlines

Step 1: Sort jobs by profit descending

Jobs order: 1(20,2) -> 2(15,2) -> 3(10,1) -> 4(5,3) -> 5(1,3)

Why: We want to pick the most profitable jobs first to maximize profit

Step 2: Schedule Job 1 at latest free slot before deadline 2 (slot 2)

Slots: 1 -> [2: Job1] -> 3 -> null

Why: Slot 2 is free and before deadline 2, so assign Job 1 there

Step 3: Schedule Job 2 at latest free slot before deadline 2 (slot 1)

[1: Job2] -> [2: Job1] -> 3 -> null

Why: Slot 2 is taken, so assign Job 2 to slot 1 which is free and before deadline 2

Step 4: Try to schedule Job 3 before deadline 1 (slot 1 taken)

[1: Job2] -> [2: Job1] -> 3 -> null

Why: Slot 1 is occupied, no free slot before deadline 1, so skip Job 3

Step 5: Schedule Job 4 at latest free slot before deadline 3 (slot 3)

[1: Job2] -> [2: Job1] -> [3: Job4] -> null

Why: Slot 3 is free and before deadline 3, assign Job 4 there

Step 6: Try to schedule Job 5 before deadline 3 (slots 1,2,3 taken)

[1: Job2] -> [2: Job1] -> [3: Job4] -> null

Why: No free slot before deadline 3, skip Job 5

Result:

Slots: [1: Job2] -> [2: Job1] -> [3: Job4] -> null
Total profit = 15 + 20 + 5 = 40

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

typedef struct Job {
    int id;
    int deadline;
    int profit;
} Job;

// Compare function for qsort to sort jobs by profit descending
int compare(const void *a, const void *b) {
    Job *jobA = (Job *)a;
    Job *jobB = (Job *)b;
    return jobB->profit - jobA->profit;
}

// Function to find max deadline
int findMaxDeadline(Job jobs[], int n) {
    int max = 0;
    for (int i = 0; i < n; i++) {
        if (jobs[i].deadline > max) {
            max = jobs[i].deadline;
        }
    }
    return max;
}

// Job Scheduling function
void jobScheduling(Job jobs[], int n) {
    // Sort jobs by profit descending
    qsort(jobs, n, sizeof(Job), compare);

    int maxDeadline = findMaxDeadline(jobs, n);

    // Initialize time slots to -1 (free)
    int *slots = (int *)malloc(maxDeadline * sizeof(int));
    for (int i = 0; i < maxDeadline; i++) {
        slots[i] = -1;
    }

    int totalProfit = 0;
    int countJobs = 0;

    // Iterate over jobs
    for (int i = 0; i < n; i++) {
        // Find a free slot for this job, starting from last possible slot
        for (int j = jobs[i].deadline - 1; j >= 0; j--) {
            if (slots[j] == -1) {
                slots[j] = jobs[i].id; // Assign job id to slot
                totalProfit += jobs[i].profit;
                countJobs++;
                break; // Move to next job
            }
        }
    }

    // Print scheduled jobs in order of slots
    printf("Scheduled Jobs in slots:\n");
    for (int i = 0; i < maxDeadline; i++) {
        if (slots[i] != -1) {
            printf("Slot %d: Job %d\n", i + 1, slots[i]);
        } else {
            printf("Slot %d: Free\n", i + 1);
        }
    }
    printf("Total jobs scheduled: %d\n", countJobs);
    printf("Total profit: %d\n", totalProfit);

    free(slots);
}

int main() {
    Job jobs[] = {
        {1, 2, 20},
        {2, 2, 15},
        {3, 1, 10},
        {4, 3, 5},
        {5, 3, 1}
    };
    int n = sizeof(jobs) / sizeof(jobs[0]);

    jobScheduling(jobs, n);

    return 0;
}

qsort(jobs, n, sizeof(Job), compare);

sort jobs by profit descending to prioritize high profit jobs

for (int j = jobs[i].deadline - 1; j >= 0; j--) {

search for latest free slot before job deadline

if (slots[j] == -1) {

check if slot is free

slots[j] = jobs[i].id;

assign job to slot

totalProfit += jobs[i].profit;

add job profit to total

countJobs++;

increment count of scheduled jobs

break;

stop searching slots after scheduling job

Output

Scheduled Jobs in slots:

Slot 1: Job 2

Slot 2: Job 1

Slot 3: Job 4

Total jobs scheduled: 3

Total profit: 40

Complexity Analysis

Time: O(n log n) because we sort the jobs by profit, then for each job we scan slots up to its deadline which is at most maxDeadline ≤ n

Space: O(n) for the slots array to track scheduled jobs

vs Alternative: Naive approach tries all permutations of jobs which is factorial time; this greedy method is efficient and practical

Edge Cases

No jobs

No scheduling happens, output shows all slots free or no slots

DSA C

qsort(jobs, n, sizeof(Job), compare);

All jobs have deadline 1

Only one job with highest profit is scheduled, others skipped

DSA C

for (int j = jobs[i].deadline - 1; j >= 0; j--) {

Multiple jobs with same deadline and profit

Jobs are scheduled in order they appear after sorting; ties broken by input order

DSA C

qsort(jobs, n, sizeof(Job), compare);

When to Use This Pattern

When you need to schedule tasks with deadlines to maximize profit or count, use the greedy job scheduling pattern by sorting jobs by profit and placing them in latest free slots before deadlines.

Common Mistakes

Mistake: Scheduling jobs in order of deadlines instead of profit
Fix: Sort jobs by profit descending first to prioritize high profit jobs

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

Mistake: Not checking if slot is free before assigning job
Fix: Check if slot is -1 (free) before assignment

Summary

Schedules jobs to maximize total profit by assigning each job to the latest free slot before its deadline.

Use when you have tasks with deadlines and profits and want to maximize profit by scheduling without conflicts.

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

Practice

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

easy

A. Maximize the number of jobs without considering profit

B. Minimize the number of jobs scheduled

C. Schedule jobs in the order they appear without considering deadlines

D. Maximize the total profit by scheduling jobs within their deadlines

Solution

1. Step 1: Understand the problem objective

   The problem asks to schedule jobs so that the total profit is maximized while respecting each job's deadline.

2. Step 2: Identify the goal

   The goal is to select jobs that fit within their deadlines and yield the highest total profit.

3. Final Answer:

   Maximize the total profit by scheduling jobs within their deadlines -> Option D

4. Quick Check:

   Goal = Maximize profit within deadlines [OK]

Hint: Focus on maximizing profit while meeting deadlines [OK]

Common Mistakes:

• Ignoring deadlines and scheduling all jobs
• Trying to minimize jobs instead of maximizing profit
• Scheduling jobs without considering profit

2. Which of the following is the correct way to sort jobs by profit in descending order in C?

easy

A. sort(jobs, n, sizeof(Job), compareProfitDesc);

B. sort(jobs, jobs+n, compareProfitDesc);

C. qsort(jobs, n, sizeof(Job), compareProfitDesc);

D. qsort(jobs, n, sizeof(Job), compareProfitAsc);

Solution

1. Step 1: Identify the sorting function in C

   In C, qsort is used for sorting arrays with a comparator function.

2. Step 2: Check the correct parameters

   The correct call is qsort(array, number_of_elements, size_of_element, comparator_function). qsort(jobs, n, sizeof(Job), compareProfitDesc); matches this.

3. Final Answer:

   qsort(jobs, n, sizeof(Job), compareProfitDesc); -> Option C

4. Quick Check:

   Use qsort with correct parameters in C [OK]

Hint: Use qsort with array, count, size, comparator in C [OK]

Common Mistakes:

• Using C++ sort() in C code
• Passing wrong size or count parameters
• Using ascending comparator instead of descending

3. Given jobs with profits and deadlines: {Job1: profit=20, deadline=2}, {Job2: profit=15, deadline=2}, {Job3: profit=10, deadline=1}, {Job4: profit=5, deadline=3}, what is the maximum total profit after scheduling?

medium

A. 40

B. 45

C. 50

D. 35

Solution

1. Step 1: Sort jobs by profit descending

   Order: Job1(20,2), Job2(15,2), Job3(10,1), Job4(5,3)

2. Step 2: Schedule jobs greedily within deadlines

   Schedule Job1 at slot 2, Job2 at slot 1 (since slot 2 taken), Job4 at slot 3. Job3 cannot be scheduled (slot 1 taken). Total profit = 20+15+5=40.

3. Final Answer:

   40 -> Option A

4. Quick Check:

   Greedy scheduling = 40 profit [OK]

Hint: Schedule highest profit jobs first within deadlines [OK]

Common Mistakes:

• Scheduling jobs ignoring deadlines
• Overlapping jobs in same slot
• Counting all jobs without checking slot availability

4. Identify the error in this C code snippet for job scheduling:

for (int i = 0; i < n; i++) {
  int slot = jobs[i].deadline - 1;
  while (slot >= 0 && result[slot] != -1) {
    slot--;
  }
  if (slot >= 0) {
    result[slot] = i;
  }
}

medium

A. The loop should start from the last job, not the first

B. The array 'result' is not initialized to -1 before use

C. The condition 'slot >= 0' should be 'slot > 0'

D. The deadline should not be decremented by 1

Solution

1. Step 1: Check initialization of result array

   The array 'result' stores scheduled jobs. It must be initialized to -1 to mark free slots.

2. Step 2: Identify missing initialization

   The code snippet does not show initialization of 'result' to -1, which can cause incorrect scheduling.

3. Final Answer:

   The array 'result' is not initialized to -1 before use -> Option B

4. Quick Check:

   Initialize result array to -1 before scheduling [OK]

Hint: Always initialize scheduling array slots to -1 [OK]

Common Mistakes:

• Forgetting to initialize result array
• Wrong loop direction for scheduling
• Incorrect slot boundary conditions

5. You have 4 jobs: J1(profit=100, deadline=2), J2(profit=19, deadline=1), J3(profit=27, deadline=2), J4(profit=25, deadline=1). Using the job scheduling algorithm, what is the maximum profit and which jobs are scheduled?

hard

A. Profit=127; Jobs scheduled: J1 at slot 2, J3 at slot 1

B. Profit=144; Jobs scheduled: J1 at slot 2, J3 at slot 1, J2 at slot 1

C. Profit=125; Jobs scheduled: J1 at slot 1, J4 at slot 2

D. Profit=100; Jobs scheduled: J1 only

Solution

1. Step 1: Sort jobs by profit descending

   Order: J1(100,2), J3(27,2), J4(25,1), J2(19,1)

2. Step 2: Schedule jobs greedily within deadlines

   Schedule J1 at slot 2, J3 at slot 1 (slot 1 free). J4 and J2 cannot be scheduled as slot 1 is taken. Total profit = 100 + 27 = 127.

3. Final Answer:

   Profit=127; Jobs scheduled: J1 at slot 2, J3 at slot 1 -> Option A

4. Quick Check:

   Greedy scheduling = 127 profit [OK]

Hint: Schedule highest profit jobs first, fill latest slots [OK]

Common Mistakes:

• Scheduling multiple jobs in same slot
• Ignoring deadlines when scheduling
• Adding profits of unscheduled jobs