Job Scheduling with Deadlines in DSA Rust

Mental Model

We want to do jobs in order to get the most reward before their deadlines. We pick jobs that fit in time and give the highest reward.

Analogy: Imagine you have a list of tasks to do before certain times, and each task gives you some money. You want to pick tasks to do so you earn the most money without missing deadlines.

Jobs: [Job1(deadline=2, profit=50), Job2(deadline=1, profit=20), Job3(deadline=2, profit=100)]
Time slots: 1 -> 2 -> 3 -> null
Schedule: [ ] -> [ ] -> [ ]

Dry Run Walkthrough

Input: jobs: [(id=1, deadline=2, profit=50), (id=2, deadline=1, profit=20), (id=3, deadline=2, profit=100)]

Goal: Schedule jobs to maximize total profit without missing deadlines

Step 1: Sort jobs by profit descending

Jobs sorted: [(3, deadline=2, profit=100), (1, deadline=2, profit=50), (2, deadline=1, profit=20)]

Why: We want to try scheduling the most profitable jobs first

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

Schedule: [ ] -> [3] -> [ ]

Why: Slot 2 is free and before deadline 2, so assign job 3 there

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

Schedule: [1] -> [3] -> [ ]

Why: Slot 2 is taken, try slot 1 which is free and before deadline 2

Step 4: Try to schedule job 2 at latest free slot before deadline 1 (slot 1)

Schedule: [1] -> [3] -> [ ]

Why: Slot 1 is taken, no free slot before deadline 1, so skip job 2

Result:

Schedule: [1] -> [3] -> [ ]
Total profit: 150

Annotated Code

DSA Rust

use std::cmp::Reverse;

#[derive(Debug)]
struct Job {
    id: usize,
    deadline: usize,
    profit: usize,
}

fn job_scheduling(jobs: &mut Vec<Job>) -> (Vec<Option<usize>>, usize) {
    // Sort jobs by profit descending
    jobs.sort_by_key(|job| Reverse(job.profit));

    // Find max deadline to size schedule
    let max_deadline = jobs.iter().map(|job| job.deadline).max().unwrap_or(0);

    // Initialize schedule slots with None
    let mut schedule = vec![None; max_deadline];
    let mut total_profit = 0;

    for job in jobs.iter() {
        // Try to find a free slot from job.deadline down to 1
        for slot in (0..job.deadline).rev() {
            if schedule[slot].is_none() {
                schedule[slot] = Some(job.id);
                total_profit += job.profit;
                break; // scheduled this job
            }
        }
    }

    (schedule, total_profit)
}

fn main() {
    let mut jobs = vec![
        Job { id: 1, deadline: 2, profit: 50 },
        Job { id: 2, deadline: 1, profit: 20 },
        Job { id: 3, deadline: 2, profit: 100 },
    ];

    let (schedule, total_profit) = job_scheduling(&mut jobs);

    // Print schedule
    let schedule_str: Vec<String> = schedule
        .iter()
        .map(|slot| match slot {
            Some(id) => id.to_string(),
            None => "_".to_string(),
        })
        .collect();

    println!("Schedule: {}", schedule_str.join(" -> "));
    println!("Total profit: {}", total_profit);
}

jobs.sort_by_key(|job| Reverse(job.profit));

Sort jobs by profit descending to prioritize high profit jobs

let max_deadline = jobs.iter().map(|job| job.deadline).max().unwrap_or(0);

Find the maximum deadline to size the schedule array

let mut schedule = vec![None; max_deadline];

Create schedule slots initialized as empty

for job in jobs.iter() {

Iterate over jobs in order of profit

for slot in (0..job.deadline).rev() {

Try to find latest free slot before job deadline

if schedule[slot].is_none() {

Check if slot is free

schedule[slot] = Some(job.id);

Assign job to slot

total_profit += job.profit;

Add job profit to total

break;

Stop searching slots after scheduling job

Output

Schedule: 1 -> 3

Total profit: 150

Complexity Analysis

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

Space: O(n) for the schedule array to hold job assignments up to max deadline

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

Edge Cases

No jobs

Returns empty schedule and zero profit

DSA Rust

let max_deadline = jobs.iter().map(|job| job.deadline).max().unwrap_or(0);

Jobs with deadlines larger than max deadline

Schedule size matches max deadline; jobs with larger deadlines are scheduled only up to max deadline slots

DSA Rust

let max_deadline = jobs.iter().map(|job| job.deadline).max().unwrap_or(0);

Multiple jobs with same deadline and profit

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

DSA Rust

jobs.sort_by_key(|job| Reverse(job.profit));

When to Use This Pattern

When you need to schedule tasks with deadlines to maximize profit or value, 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 deadline instead of profit
Fix: Sort jobs by profit descending to prioritize high reward jobs

Mistake: Assigning jobs to earliest free slot instead of latest before deadline
Fix: Try slots from deadline backward to maximize slot usage

Mistake: Not handling empty job list causing panic on max deadline
Fix: Use unwrap_or(0) when finding max deadline to handle empty input

Summary

Schedules jobs to maximize total profit without missing deadlines.

Use when you have tasks with deadlines and profits and want the best total reward.

Sort jobs by profit and assign each to the latest free slot before its deadline.

Practice

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

easy

A. Schedule jobs in the order they arrive without considering deadlines

B. Minimize the number of jobs scheduled

C. Maximize total profit by scheduling jobs before their deadlines

D. Maximize the number of jobs scheduled regardless of profit

Solution

1. Step 1: Understand the problem goal

   The problem asks to schedule jobs so that each job finishes before its deadline and the total profit is maximized.

2. Step 2: Identify the objective

   Maximizing total profit means choosing jobs with higher profit and fitting them before their deadlines.

3. Final Answer:

   Maximize total profit by scheduling jobs before their deadlines -> Option C

4. Quick Check:

   Goal = Maximize profit before deadlines [OK]

Hint: Focus on profit maximization within deadlines [OK]

Common Mistakes:

• Thinking the goal is to schedule all jobs
• Ignoring deadlines when scheduling
• Trying to minimize jobs instead of maximizing profit

2. Which Rust data structure is best suited to keep track of free time slots when implementing job scheduling with deadlines?

easy

A. Vec (vector) with boolean flags for slots

B. HashMap with job IDs as keys

C. LinkedList of jobs sorted by profit

D. BinaryHeap for storing jobs by deadline

Solution

1. Step 1: Identify the need for tracking free slots

   We need to know which time slots are free to schedule jobs before their deadlines.

2. Step 2: Choose a data structure for slot tracking

   A vector of booleans can mark each slot as free or occupied efficiently.

3. Final Answer:

   Vec (vector) with boolean flags for slots -> Option A

4. Quick Check:

   Use Vec<bool> to track free slots [OK]

Hint: Use a boolean vector to mark free/occupied slots [OK]

Common Mistakes:

• Using HashMap which is unnecessary for fixed slots
• Using LinkedList which is inefficient for slot checking
• Using BinaryHeap which is for priority, not slot tracking

3. What is the output of the following Rust code snippet that schedules jobs with deadlines and profits?

struct Job { id: char, deadline: usize, profit: usize }

fn job_scheduling(jobs: &mut Vec<Job>) -> Vec<char> {
    jobs.sort_by(|a, b| b.profit.cmp(&a.profit));
    let max_deadline = jobs.iter().map(|j| j.deadline).max().unwrap_or(0);
    let mut slots = vec![false; max_deadline];
    let mut result = Vec::new();

    for job in jobs.iter() {
        for slot in (0..job.deadline).rev() {
            if !slots[slot] {
                slots[slot] = true;
                result.push(job.id);
                break;
            }
        }
    }
    result
}

fn main() {
    let mut jobs = vec![
        Job { id: 'A', deadline: 2, profit: 100 },
        Job { id: 'B', deadline: 1, profit: 19 },
        Job { id: 'C', deadline: 2, profit: 27 },
        Job { id: 'D', deadline: 1, profit: 25 },
        Job { id: 'E', deadline: 3, profit: 15 },
    ];
    let scheduled = job_scheduling(&mut jobs);
    println!("{:?}", scheduled);
}

medium

A. ['A', 'B', 'E']

B. ['A', 'D', 'E']

C. ['B', 'D', 'E']

D. ['A', 'C', 'E']

Solution

1. Step 1: Sort jobs by profit descending

   Sorted jobs: A(100,2), C(27,2), D(25,1), B(19,1), E(15,3)

2. Step 2: Schedule jobs in latest free slot before deadline

   Schedule A at slot 1 (0-based), C at slot 0, E at slot 2. D and B cannot be scheduled as slots 0 and 1 are taken.

3. Final Answer:

   ['A', 'C', 'E'] -> Option D

4. Quick Check:

   Jobs scheduled = ['A', 'C', 'E'] [OK]

Hint: Sort by profit, assign latest free slot before deadline [OK]

Common Mistakes:

• Scheduling jobs in arrival order instead of profit order
• Assigning earliest slot instead of latest free slot
• Ignoring slot availability and deadlines

4. Identify the bug in this Rust code snippet for job scheduling with deadlines:

fn schedule_jobs(jobs: &mut Vec<(char, usize, usize)>) -> Vec<char> {
    jobs.sort_by(|a, b| b.2.cmp(&a.2));
    let max_deadline = jobs.iter().map(|j| j.1).max().unwrap_or(0);
    let mut slots = vec![false; max_deadline];
    let mut result = Vec::new();

    for job in jobs.iter() {
        for slot in 0..job.1 {
            if !slots[slot] {
                slots[slot] = true;
                result.push(job.0);
                break;
            }
        }
    }
    result
}

medium

A. Jobs are sorted by profit ascending instead of descending

B. Inner loop should iterate slots in reverse order to assign latest slot

C. Result vector should store job profits instead of IDs

D. Slots vector size is incorrect, should be max_deadline + 1

Solution

1. Step 1: Check sorting order

   Jobs are sorted by profit descending (b.2.cmp(&a.2)), which is correct to prioritize high-profit jobs.

2. Step 2: Check slot assignment loop

   The loop iterates from 0 to deadline-1, assigning the earliest available slot. The correct approach assigns the latest free slot before the deadline to leave earlier slots for future jobs with tighter deadlines, so the loop should be reversed using (0..job.1).rev().

3. Final Answer:

   Inner loop should iterate slots in reverse order to assign latest slot -> Option B

4. Quick Check:

   Assign latest free slot by looping backwards [OK]

Hint: Loop slots backward to assign latest free slot [OK]

Common Mistakes:

• Assigning earliest slot instead of latest free slot
• Using wrong slot vector size (off-by-one)
• Storing wrong data in result vector

5. Given jobs with deadlines and profits: A(4, 70), B(1, 80), C(1, 30), D(2, 100), E(3, 40), how many jobs can be scheduled to maximize profit and what is the total profit? Use the job scheduling with deadlines approach.

hard

A. 4 jobs, total profit 290

B. 3 jobs, total profit 250

C. 3 jobs, total profit 220

D. 4 jobs, total profit 240

Solution

1. Step 1: Sort jobs by profit descending

   Sorted: D(100,2), B(80,1), A(70,4), E(40,3), C(30,1)

2. Step 2: Schedule jobs in latest free slot before deadline

   Schedule B at slot 0 (deadline 1), D at slot 1 (deadline 2), E at slot 2 (deadline 3), A at slot 3 (deadline 4). C cannot be scheduled as slot 0 is taken.

3. Step 3: Calculate total profit

   Profits: B(80) + D(100) + E(40) + A(70) = 290

4. Final Answer:

   4 jobs, total profit 290 -> Option A

5. Quick Check:

   4 jobs scheduled, profit = 290 [OK]

Hint: Sort by profit, assign latest free slot before deadline [OK]

Common Mistakes:

• Scheduling fewer jobs than possible
• Ignoring slot availability and deadlines
• Adding profits of unscheduled jobs