The following code attempts to solve the job scheduling problem optimally. Which line contains a subtle bug that can cause incorrect results?

medium🐞 Bug Identification Q14 of Q15

Dynamic Programming: Knapsack - Maximum Profit in Job Scheduling

ALine 11: Using bisect_right to find compatible job index

BLine 7: Creating ends array from job end times

CLine 4: Sorting jobs by start time instead of end time

DLine 14: Calculating dp[i] as max of take and skip

Step-by-Step Solution

Step 1: Identify sorting criteria
Jobs must be sorted by end time for binary search on ends array to work correctly.
Step 2: Check sorting line
Line 4 sorts by start time, breaking DP dependencies and binary search correctness.
Final Answer:
Option C -> Option C
Quick Check:
Sorting by start time causes incorrect compatible job lookups and suboptimal profits [OK]

Quick Trick: Sort jobs by end time, not start time [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Sorting by start time looks reasonable but breaks the DP logic relying on end time ordering.

Interviewer Note:

CONTEXT

Tests if candidate spots subtle but critical sorting bug that breaks correctness.

Master "Maximum Profit in Job Scheduling" in Dynamic Programming: Knapsack

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

More Dynamic Programming: Knapsack Quizzes