Job Scheduling with Deadlines in DSA C - Build from Scratch

Job Scheduling with Deadlines

📖 Scenario: You are managing a small workshop where different jobs need to be completed. Each job has a deadline and a profit if finished on time. You want to schedule the jobs to maximize your total profit without missing deadlines.

🎯 Goal: Build a program that schedules jobs with deadlines to maximize profit. You will create the job data, set the maximum deadline, implement the scheduling logic, and print the scheduled jobs.

📋 What You'll Learn

Create an array of jobs with exact job IDs, deadlines, and profits

Create an integer variable for the maximum deadline

Implement the job scheduling logic to select jobs maximizing profit without missing deadlines

Print the scheduled job IDs in order of their scheduled time slots

💡 Why This Matters

🌍 Real World

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

💼 Career

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

1

Create the Job Data Structure and Jobs Array

Define a struct Job with int id, int deadline, and int profit. Then create an array called jobs with these exact entries: {1, 4, 20}, {2, 1, 10}, {3, 1, 40}, {4, 1, 30}.

DSA C

# Define struct Job and create jobs array with given entries
// Your code here

Hint

Use struct to define the job with three fields. Then create an array with the exact jobs listed.

2

Set the Maximum Deadline Variable

Create an integer variable called max_deadline and set it to 4.

DSA C

#include 

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

struct Job jobs[] = {
    {1, 4, 20},
    {2, 1, 10},
    {3, 1, 40},
    {4, 1, 30}
};

int n = sizeof(jobs) / sizeof(jobs[0]);

// Create max_deadline variable and set to 4
// Your code here

Hint

Just create an integer variable named max_deadline and assign it the value 4.

3

Implement Job Scheduling Logic

Write a function called jobScheduling that takes the jobs array, n, and max_deadline. It should schedule jobs to maximize profit without missing deadlines. Use a simple greedy approach: sort jobs by profit descending, then assign each job to the latest free slot before its deadline. Store scheduled job IDs in an array called result. Implement the scheduling logic inside jobScheduling.

DSA C

void swap(struct Job* a, struct Job* b) {
    struct Job temp = *a;
    *a = *b;
    *b = temp;
}
void sortJobsByProfit(struct Job arr[], int n) {
    for (int i = 0; i  0; j--) {
            if (slot[j] == 0) {
                slot[j] = 1; // mark slot as occupied
                result[j - 1] = jobs[i].id;
                break;
            }
        }
    }
}
// Create result array, call jobScheduling, and print scheduled jobs

Hint

Sort jobs by profit descending. Then for each job, find the latest free slot before its deadline and assign it. Use an array to track free slots.

4

Print Scheduled Jobs

Create an integer array result of size max_deadline initialized with zeros. Call jobScheduling(jobs, n, max_deadline, result). Then print the scheduled job IDs in order separated by spaces using printf. Skip zeros (empty slots).

DSA C

Hint

Initialize the result array with zeros. Call jobScheduling. Then print the job IDs in order, skipping zeros.