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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Job Scheduling with Deadlines - Simple Case

What is the output of the following Rust code that schedules jobs with deadlines to maximize profit?

DSA Rust

use std::cmp::Ordering;

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

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

    for job in jobs.iter() {
        for slot in (0..job.deadline).rev() {
            if result[slot].is_none() {
                result[slot] = Some(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 schedule = job_scheduling(&mut jobs);
    println!("{:?}", schedule);
}

A [Some('c'), Some('a'), Some('e')]

B [Some('a'), Some('d'), Some('e')]

C [Some('a'), Some('b'), Some('e')]

D [Some('c'), Some('d'), Some('e')]

💡 Hint

Jobs are scheduled in order of descending profit, filling the latest available slot before their deadline.

The jobs are sorted by profit: a(100), c(27), d(25), b(19), e(15).

Schedule 'a' at slot 1 (deadline 2), 'c' at slot 0 (deadline 2), and 'e' at slot 2 (deadline 3). Slots are zero-indexed.

❓ Predict Output

intermediate

Number of Jobs Scheduled in Overlapping Deadlines

Given the Rust code below, how many jobs are scheduled successfully?

DSA Rust

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

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

    for job in jobs.iter() {
        for slot in (0..job.deadline).rev() {
            if result[slot].is_none() {
                result[slot] = Some(job.id);
                count += 1;
                break;
            }
        }
    }
    count
}

fn main() {
    let mut jobs = vec![
        Job { id: 'x', deadline: 1, profit: 20 },
        Job { id: 'y', deadline: 2, profit: 15 },
        Job { id: 'z', deadline: 2, profit: 10 },
        Job { id: 'w', deadline: 1, profit: 5 },
    ];
    let scheduled_count = job_scheduling(&mut jobs);
    println!("{}", scheduled_count);
}

A 1

B 3

C 4

D 2

💡 Hint

Count how many unique slots can be filled before their deadlines.

Jobs sorted by profit: x(20), y(15), z(10), w(5).

Slot 0 (deadline 1) assigned to 'x'.

Slot 1 (deadline 2) assigned to 'y'.

Slot 0 is taken, so 'z' cannot be scheduled at slot 0 but can be at slot 1 which is taken, so 'z' is skipped.

'w' has deadline 1 but slot 0 is taken, so skipped.

Total scheduled jobs: 2 ('x' and 'y').

🔧 Debug

advanced

Identify the Bug in Job Scheduling Code

What error will the following Rust code produce when run?

DSA Rust

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

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

    for job in jobs.iter() {
        for slot in (0..job.deadline).rev() {
            if result[slot].is_none() {
                result[slot] = Some(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 },
    ];
    let schedule = job_scheduling(&mut jobs);
    println!("{:?}", schedule);
}

A No error; outputs [Some('b'), Some('c')]

B No error; outputs [Some('c'), Some('a')]

C Logic error: jobs sorted ascending by profit, so low profit jobs scheduled first

D Runtime panic due to index out of bounds

💡 Hint

Check the sorting order of jobs by profit.

The code sorts jobs by ascending profit (lowest first), which is incorrect for maximizing profit.

This causes low profit jobs to be scheduled first, potentially blocking higher profit jobs.

There is no runtime error or panic.

🧠 Conceptual

advanced

Maximum Profit Calculation in Job Scheduling

Given a set of jobs with deadlines and profits, which approach correctly calculates the maximum total profit achievable by scheduling jobs before their deadlines?

A Sort jobs by descending profit and schedule each job in the latest available slot before its deadline

B Sort jobs by ascending deadline and schedule earliest deadline jobs first

C Schedule jobs in the order they appear without sorting

D Sort jobs by ascending profit and schedule each job in the earliest available slot

💡 Hint

Think about how to maximize profit by prioritizing jobs.

Sorting jobs by descending profit ensures the most profitable jobs are scheduled first.

Scheduling each job in the latest available slot before its deadline allows more jobs to fit.

Other options do not guarantee maximum profit.

🚀 Application

expert

Output of Job Scheduling with Complex Deadlines and Profits

What is the output of the following Rust code that schedules jobs with deadlines and profits? Show the scheduled jobs in order of their slots.

DSA Rust

use std::cmp::Ordering;

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

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

    for job in jobs.iter() {
        for slot in (0..job.deadline).rev() {
            if result[slot].is_none() {
                result[slot] = Some(job.id);
                break;
            }
        }
    }
    result
}

fn main() {
    let mut jobs = vec![
        Job { id: 'p', deadline: 3, profit: 40 },
        Job { id: 'q', deadline: 1, profit: 100 },
        Job { id: 'r', deadline: 2, profit: 20 },
        Job { id: 's', deadline: 2, profit: 30 },
        Job { id: 't', deadline: 1, profit: 10 },
    ];
    let schedule = job_scheduling(&mut jobs);
    println!("{:?}", schedule);
}

A [Some('q'), Some('p'), Some('s')]

B [Some('q'), Some('s'), Some('p')]

C [Some('q'), Some('r'), Some('p')]

D [Some('p'), Some('q'), Some('s')]

💡 Hint

Schedule jobs by descending profit, placing each in the latest free slot before deadline.

Jobs sorted by profit: q(100), p(40), s(30), r(20), t(10).

Slot 0 (deadline 1) assigned to 'q'.

Slot 2 (deadline 3) assigned to 'p'.

Slot 1 (deadline 2) assigned to 's'.

Jobs 'r' and 't' cannot be scheduled as slots are occupied.

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