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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Job Scheduling with Deadlines and Profits

What is the output of the following Python code that schedules jobs to maximize profit given deadlines?

DSA Python

def job_scheduling(jobs):
    n = len(jobs)
    jobs.sort(key=lambda x: x[2], reverse=True)  # Sort by profit descending
    result = [False] * n
    slot = [-1] * n
    for i in range(n):
        for j in range(min(n, jobs[i][1]) - 1, -1, -1):
            if not result[j]:
                result[j] = True
                slot[j] = jobs[i][0]
                break
    return [job for job in slot if job != -1]

jobs = [('a', 2, 100), ('b', 1, 19), ('c', 2, 27), ('d', 1, 25), ('e', 3, 15)]
print(job_scheduling(jobs))

A ['c', 'a', 'e']

B ['a', 'b', 'e']

C ['a', 'c', 'e']

D ['c', 'd', 'e']

💡 Hint

Sort jobs by profit descending and assign each job to the latest available slot before its deadline.

The code sorts jobs by profit descending. It tries to schedule each job in the latest free slot before its deadline. The jobs 'a', 'c', and 'e' get scheduled, maximizing profit.

🧠 Conceptual

intermediate

Maximum Number of Jobs Scheduled

Given the jobs with deadlines and profits, what is the maximum number of jobs that can be scheduled without missing deadlines?

A 3

B 4

C 5

D 2

💡 Hint

The maximum number of jobs scheduled equals the number of available time slots before deadlines.

Since the maximum deadline is 3, at most 3 jobs can be scheduled without overlapping deadlines.

🔧 Debug

advanced

Identify the Error in Job Scheduling Code

What error will the following code produce when run?

DSA Python

def job_scheduling(jobs):
    n = len(jobs)
    jobs.sort(key=lambda x: x[2])  # Sort by profit ascending (incorrect)
    result = [False] * n
    slot = [-1] * n
    for i in range(n):
        for j in range(min(n, jobs[i][1]) - 1, -1, -1):
            if not result[j]:
                result[j] = True
                slot[j] = jobs[i][0]
                break
    return [job for job in slot if job != -1]

jobs = [('a', 2, 100), ('b', 1, 19), ('c', 2, 27), ('d', 1, 25), ('e', 3, 15)]
print(job_scheduling(jobs))

A ['b', 'c', 'e']

B ['a', 'd', 'e']

C ['e', 'd', 'b']

D ['a', 'c', 'e']

💡 Hint

Check the sorting order of jobs by profit.

The code sorts jobs by profit ascending, so it schedules low profit jobs first, resulting in ['b', 'c', 'e'].

❓ Predict Output

advanced

Output of Job Scheduling with Overlapping Deadlines

What is the output of this code scheduling jobs with overlapping deadlines and profits?

DSA Python

def job_scheduling(jobs):
    n = len(jobs)
    jobs.sort(key=lambda x: x[2], reverse=True)
    result = [False] * n
    slot = [-1] * n
    for i in range(n):
        for j in range(min(n, jobs[i][1]) - 1, -1, -1):
            if not result[j]:
                result[j] = True
                slot[j] = jobs[i][0]
                break
    return [job for job in slot if job != -1]

jobs = [('x', 1, 20), ('y', 2, 15), ('z', 2, 10), ('w', 1, 5)]
print(job_scheduling(jobs))

A ['x', 'z']

B ['w', 'y']

C ['y', 'x']

D ['x', 'y']

💡 Hint

Schedule jobs by highest profit first and assign to latest free slot before deadline.

Jobs 'x' and 'y' are scheduled because they have highest profits and fit in slots 0 and 1 respectively.

🧠 Conceptual

expert

Optimal Strategy for Job Scheduling with Deadlines

Which strategy guarantees maximum total profit when scheduling jobs with deadlines and profits?

A Schedule jobs in input order without sorting

B Sort jobs by descending profit and schedule each in latest free slot before deadline

C Sort jobs by earliest deadline and schedule in that order

D Sort jobs by ascending profit and schedule in earliest free slot

💡 Hint

Think about maximizing profit while respecting deadlines.

Sorting by descending profit and placing each job in the latest free slot before its deadline ensures maximum profit.

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. Maximize the total profit by scheduling jobs before their deadlines

C. Minimize the number of jobs scheduled

D. Maximize the number of jobs scheduled regardless of profit

Solution

1. Step 1: Understand the problem goal

   The problem aims to schedule jobs so that each job finishes before its deadline.

2. Step 2: Identify the optimization criteria

   We want to maximize the total profit earned from scheduled jobs, not just the count.

3. Final Answer:

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

4. Quick Check:

   Goal = Maximize profit [OK]

Hint: Focus on maximizing profit within deadlines [OK]

Common Mistakes:

• Thinking it's about scheduling all jobs regardless of profit
• Confusing deadline with job duration
• Assuming jobs can be scheduled after deadlines

2. Which of the following is the correct Python syntax to sort a list of jobs by their profit in descending order? Assume each job is a tuple (job_id, deadline, profit).

easy

A. jobs.sort(key=lambda x: x[2], reverse=True)

B. jobs.sort(key=lambda x: x[1], reverse=True)

C. jobs.sort(reverse=True, key=lambda x: x[0])

D. jobs.sort(key=lambda x: x[2])

Solution

1. Step 1: Identify the sorting key

   Profit is at index 2 in each job tuple, so key=lambda x: x[2] is correct.

2. Step 2: Sort in descending order

   Use reverse=True to sort profits from highest to lowest.

3. Final Answer:

   jobs.sort(key=lambda x: x[2], reverse=True) -> Option A

4. Quick Check:

   Sort by profit descending = jobs.sort(key=lambda x: x[2], reverse=True) [OK]

Hint: Sort by profit descending using key and reverse=True [OK]

Common Mistakes:

• Sorting by deadline instead of profit
• Forgetting reverse=True for descending order
• Using wrong tuple index for profit

3. What is the output of the following code snippet?

jobs = [(1, 4, 20), (2, 1, 10), (3, 1, 40), (4, 1, 30)]
jobs.sort(key=lambda x: x[2], reverse=True)
slots = [False] * 4
result = [None] * 4
for job in jobs:
    for j in range(min(4, job[1]) - 1, -1, -1):
        if not slots[j]:
            slots[j] = True
            result[j] = job[0]
            break
print(result)

medium

A. [3, None, None, 1]

B. [4, 3, 1, None]

C. [1, 4, 3, None]

D. [None, 3, 4, 1]

Solution

1. Step 1: Sort jobs by profit descending

   Sorted jobs: (3,1,40), (4,1,30), (1,4,20), (2,1,10)

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

   Job 3: deadline 1, slot 0 free -> assign slot 0 = 3 Job 4: deadline 1, slot 0 taken, no earlier slot -> skip Job 1: deadline 4, slots 3 to 0 checked, slot 3 free -> assign slot 3 = 1 Job 2: deadline 1, slot 0 taken, no earlier slot -> skip

3. Final Answer:

   [3, None, None, 1] -> Option A

4. Quick Check:

   Result = [3, None, None, 1] [OK]

Hint: Assign jobs from highest profit to latest free slot before deadline [OK]

Common Mistakes:

• Assigning jobs to earliest slot instead of latest
• Not sorting jobs by profit first
• Confusing slot indices with deadlines

4. The following code attempts to schedule jobs with deadlines and maximize profit. What is the bug?

jobs = [(1, 2, 100), (2, 1, 19), (3, 2, 27), (4, 1, 25), (5, 3, 15)]
jobs.sort(key=lambda x: x[2])  # Sort by profit ascending
slots = [False] * 3
result = [None] * 3
for job in jobs:
    for j in range(min(3, job[1])):
        if not slots[j]:
            slots[j] = True
            result[j] = job[0]
            break
print(result)

medium

A. Result array is not initialized properly

B. Slots array size is too small

C. Inner loop should iterate backwards from deadline to 0

D. Jobs are sorted by profit ascending instead of descending

Solution

1. Step 1: Check sorting order

   Jobs are sorted by profit ascending, which schedules low profit jobs first.

2. Step 2: Understand scheduling impact

   Scheduling low profit jobs first reduces total profit; sorting must be descending.

3. Final Answer:

   Jobs are sorted by profit ascending instead of descending -> Option D

4. Quick Check:

   Sort order must be descending for max profit [OK]

Hint: Sort jobs by profit descending to maximize profit [OK]

Common Mistakes:

• Sorting by ascending profit
• Iterating slots forward instead of backward (less critical here)
• Ignoring slot size mismatch

5. Given jobs [(1, 2, 100), (2, 1, 19), (3, 2, 27), (4, 1, 25), (5, 3, 15)], what is the maximum total profit achievable by scheduling jobs before their deadlines? Assume each job takes 1 unit time and only one job can be scheduled at a time.

hard

A. 115

B. 152

C. 142

D. 127

Solution

1. Step 1: Sort jobs by profit descending

   Sorted jobs: (1,2,100), (3,2,27), (4,1,25), (2,1,19), (5,3,15)

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

   Job 1: deadline 2, assign slot 2 (index 1) Job 3: deadline 2, assign slot 1 (index 0) Job 4: deadline 1, slot 0 taken, skip Job 2: deadline 1, slot 0 taken, skip Job 5: deadline 3, assign slot 3 (index 2)

3. Step 3: Calculate total profit

   Scheduled jobs: 1 (100), 3 (27), 5 (15) Total profit = 100 + 27 + 15 = 142

4. Final Answer:

   142 -> Option C

5. Quick Check:

   Total profit = 142 [OK]

Hint: Schedule highest profit jobs first in latest free slot [OK]

Common Mistakes:

• Scheduling jobs without sorting by profit
• Assigning jobs to earliest slot instead of latest
• Counting jobs beyond deadline slots