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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Job Scheduling with Deadlines Algorithm

What is the output of the following C code that schedules jobs to maximize profit given deadlines?

DSA C

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

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

int compare(const void *a, const void *b) {
    Job *j1 = (Job *)a;
    Job *j2 = (Job *)b;
    return j2->profit - j1->profit;
}

void printJobScheduling(Job jobs[], int n) {
    qsort(jobs, n, sizeof(Job), compare);

    int result[n];
    int slot[n];

    for (int i = 0; i < n; i++)
        slot[i] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = (jobs[i].deadline < n ? jobs[i].deadline : n) - 1; j >= 0; j--) {
            if (slot[j] == 0) {
                result[j] = i;
                slot[j] = 1;
                break;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (slot[i])
            printf("%c ", jobs[result[i]].id);
    }
    printf("\n");
}

int main() {
    Job jobs[] = {{'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27}, {'d', 1, 25}, {'e', 3, 15}};
    int n = sizeof(jobs) / sizeof(jobs[0]);
    printJobScheduling(jobs, n);
    return 0;
}

A a b c

B a c e

C b d e

D a d e

💡 Hint

Jobs are sorted by profit and scheduled in the latest available slot before their deadline.

The algorithm sorts jobs by profit descending: a(100), c(27), d(25), b(19), e(15). It schedules 'a' at slot 1 (deadline 2), 'c' at slot 0 (deadline 2), and 'e' at slot 2 (deadline 3). Jobs 'd' and 'b' cannot be scheduled due to slot conflicts.

🧠 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 missing deadlines?

A 2

B 4

C 5

D 3

💡 Hint

Maximum jobs scheduled equals the number of available slots filled by the greedy algorithm.

The greedy scheduling fills 3 slots with jobs 'a', 'c', and 'e'. No more jobs can fit without missing deadlines.

🔧 Debug

advanced

Identify the Bug in Job Scheduling Code

What error will the following code produce when run?

DSA C

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

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

int compare(const void *a, const void *b) {
    Job *j1 = (Job *)a;
    Job *j2 = (Job *)b;
    return j1->profit - j2->profit; // Bug here
}

void printJobScheduling(Job jobs[], int n) {
    qsort(jobs, n, sizeof(Job), compare);

    int result[n];
    int slot[n];

    for (int i = 0; i < n; i++)
        slot[i] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = (jobs[i].deadline < n ? jobs[i].deadline : n) - 1; j >= 0; j--) {
            if (slot[j] == 0) {
                result[j] = i;
                slot[j] = 1;
                break;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (slot[i])
            printf("%c ", jobs[result[i]].id);
    }
    printf("\n");
}

int main() {
    Job jobs[] = {{'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27}, {'d', 1, 25}, {'e', 3, 15}};
    int n = sizeof(jobs) / sizeof(jobs[0]);
    printJobScheduling(jobs, n);
    return 0;
}

A The jobs are sorted in ascending profit order, causing incorrect scheduling output.

B Compilation error due to missing semicolon.

C Runtime error due to accessing invalid array index.

D No output because of infinite loop.

💡 Hint

Check the compare function used in qsort.

The compare function sorts jobs by ascending profit, not descending. This causes the greedy algorithm to schedule low-profit jobs first, resulting in suboptimal output.

📝 Syntax

advanced

Syntax Error in Job Scheduling Code

Which option contains a syntax error in the job scheduling code snippet?

DSA C

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

int compare(const void *a, const void *b) {
    Job *j1 = (Job *)a;
    Job *j2 = (Job *)b;
    return j2->profit - j1->profit;
}

void printJobScheduling(Job jobs[], int n) {
    qsort(jobs, n, sizeof(Job), compare);

    int result[n];
    int slot[n];

    for (int i = 0; i < n; i++)
        slot[i] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = (jobs[i].deadline < n ? jobs[i].deadline : n) - 1; j >= 0; j--) {
            if (slot[j] == 0) {
                result[j] = i;
                slot[j] = 1;
                break;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (slot[i])
            printf("%c ", jobs[result[i]].id);
    }
    printf("\n");
}

A Missing closing brace for printJobScheduling function.

B Incorrect pointer casting in compare function.

C Using variable length arrays without initialization.

D Missing semicolon after struct definition.

💡 Hint

Check the braces and function endings carefully.

The code snippet is missing the closing brace '}' for the printJobScheduling function, causing a syntax error.

🚀 Application

expert

Optimal Job Scheduling Result for Custom Input

Given the following jobs with deadlines and profits, which sequence of job IDs maximizes profit without missing deadlines? Jobs: {'j1', deadline=1, profit=20} {'j2', deadline=2, profit=15} {'j3', deadline=2, profit=10} {'j4', deadline=1, profit=5} {'j5', deadline=3, profit=1} Choose the correct scheduled job sequence output.

A j4 j3 j5

B j1 j3 j5

C j1 j2 j5

D j2 j3 j5

💡 Hint

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

Sorted by profit: j1(20), j2(15), j3(10), j4(5), j5(1). Schedule j1 at slot 0 (deadline 1), j2 at slot 1 (deadline 2), j5 at slot 2 (deadline 3). Jobs j3 and j4 cannot be scheduled without missing deadlines.

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