[Solved] Consider the following Python code implement... What is the value of dp[2] after the loop iteration with i=2 when the input is startTime = [1, 2, 3], endTime = [3, 5, 10], and profit = [20, 20, 100]? | Dynamic Programming: Knapsack

Dynamic Programming: Knapsack - Maximum Profit in Job Scheduling

Consider the following Python code implementing the optimal job scheduling solution. What is the value of dp[2] after the loop iteration with i=2 when the input is startTime = [1, 2, 3], endTime = [3, 5, 10], and profit = [20, 20, 100]?

A120

B20

C140

D100

Step-by-Step Solution

Step 1: Sort jobs by end time
Jobs sorted by end time: [(1,3,20), (2,5,20), (3,10,100)]. Ends = [3,5,10]
Step 2: Calculate dp[2]
For i=2 (job with start=3, end=10, profit=100): binary search idx = bisect_right(ends, 2) - 1 = 0 (job 0 compatible). take = 100 + dp[0] = 100 + 20 = 120; skip = dp[1] = max profit till job 1 = 20 (from previous iterations). dp[2] = max(120, 20) = 120.
Final Answer:
Option A -> Option A
Quick Check:
dp array after iteration 2 is [20, 20, 120] [OK]

Quick Trick: Binary search finds last compatible job index correctly [OK]

Common Mistakes:

MISTAKES

Off-by-one in binary search index
Using dp[i-1] incorrectly
Ignoring base case for dp[0]

Trap Explanation:

PITFALL

Candidates often miscalculate idx or forget to add dp[idx] profit, leading to wrong dp values.

Interviewer Note:

CONTEXT

Tests candidate's ability to trace DP with binary search and understand indexing.

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

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Dynamic Programming: Knapsack Quizzes

What is the value of dp[2] after the loop iteration with i=2 when the input is startTime = [1, 2, 3], endTime = [3, 5, 10], and profit = [20, 20, 100]?

Step 1: Sort jobs by end time

Step 2: Calculate dp[2]

Final Answer:

Quick Check:

Want More Practice?