Dynamic Programming: Knapsack - Maximum Profit in Job Scheduling
What is the output of the job scheduling code below when given a single job with startTime=[5], endTime=[5], profit=[10]?
What is the output of the job scheduling code below when given a single job with startTime=[5], endTime=[5], profit=[10]?
medium🧾 Code Trace Q4 of Q15
Step-by-Step Solution
Solution:
Step 1: Sort single job
Only one job: (5,5,10), ends=[5]Step 2: Calculate dp[0]
idx = bisect_right([5], 5-1=4) -1 = bisect_right([5],4)-1=0-1=-1; take=10+0=10; skip=0; dp[0]=max(10,0)=10Step 3: Return dp[-1]
dp[-1]=dp[0]=10Final Answer:
Option C -> Option CQuick Check:
Single job profit returned correctly [OK]
Quick Trick: Single job dp equals its profit [OK]
Common Mistakes:
MISTAKES- Miscomputing binary search index
- Assuming empty dp for single job
Trap Explanation:
PITFALL- Some candidates expect error or zero profit for single job edge case.
Interviewer Note:
CONTEXT- Tests boundary conditions and indexing correctness.
Master "Maximum Profit in Job Scheduling" in Dynamic Programming: Knapsack
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Dynamic Programming: Knapsack Quizzes