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.