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.

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