💡 Skipping job 4 yields higher profit than taking it.
reconstruct
Final result read from dp array
The maximum profit is the last value in dp array, representing best schedule profit.
💡 The dp array accumulates max profit; last cell is final answer.
Line:return dp[-1]
💡 dp[-1] = 150 is the maximum profit achievable.
from typing import List
import bisect
def jobScheduling(startTime: List[int], endTime: List[int], profit: List[int]) -> int:
jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1]) # STEP 1
n = len(jobs) # STEP 2
ends = [job[1] for job in jobs] # STEP 2
dp = [0] * n # STEP 2
for i in range(n): # STEP 3-9
start_i, end_i, profit_i = jobs[i] # STEP i
idx = bisect.bisect_right(ends, start_i - 1) - 1 # STEP i
take = profit_i + (dp[idx] if idx >= 0 else 0) # STEP i
skip = dp[i - 1] if i > 0 else 0 # STEP i
dp[i] = max(take, skip) # STEP i
return dp[-1] # STEP 10
if __name__ == '__main__':
print(jobScheduling([1,2,3,4,6], [3,5,10,6,9], [20,20,100,70,60])) # Expected 150
📊
Maximum Profit in Job Scheduling - Watch the Algorithm Execute, Step by Step
Watching each step reveals how the algorithm balances taking or skipping jobs based on compatibility and profit, making the DP logic clear without needing to read code.
Step 1/10
·Active fill★Answer cell
Initializing dp array
i\w
0
1
2
3
4
i=0
?
?
?
?
?
Job 1 (1,3,20)
Initializing dp array
i\w
0
1
2
3
4
i=0
?
?
?
?
?
dp unfilled
Item 0 - wt:3 val:20
i\w
0
1
2
3
4
i=0
20
?
?
?
?
dp[0] = 20 (take job 0)
Item 1 - wt:5 val:20
i\w
0
1
2
3
4
i=0
20
20
?
?
?
dp[1] = 20 (skip or take job 1)
Item 2 - wt:6 val:70
i\w
0
1
2
3
4
i=0
20
20
90
?
?
dp[2] = 90 (take job 2 + dp[0])
Item 3 - wt:9 val:60
i\w
0
1
2
3
4
i=0
20
20
90
?
?
Compatible job idx = 2
Item 3 - wt:9 val:60
i\w
0
1
2
3
4
i=0
20
20
90
150
?
dp[3] = 150 (take job 3 + dp[2])
Item 4 - wt:10 val:100
i\w
0
1
2
3
4
i=0
20
20
90
150
?
Compatible job idx = 0
Item 4 - wt:10 val:100
i\w
0
1
2
3
4
i=0
20
20
90
150
150
dp[4] = 150 (skip job 4)
Item 4 - wt:10 val:100
i\w
0
1
2
3
4
i=0
20
20
90
150
150
Answer: 150
Key Takeaways
✓ Sorting jobs by end time is essential for efficient compatibility checks.
Without sorting, finding compatible jobs would be inefficient and complex.
✓ The dp array stores the maximum profit achievable up to each job, reflecting cumulative decisions.
This shows how dynamic programming builds solutions incrementally.
✓ Binary search quickly finds the last compatible job, enabling O(n log n) complexity.
This optimization is key to making the algorithm efficient and practical.
Practice
(1/5)
1. Consider the following Python code implementing the space-optimized 0/1 Knapsack solution. What is the output when weights = [10, 20, 30], values = [60, 100, 120], and W = 50?
def knapsack_space_optimized(weights, values, W):
n = len(weights)
dp = [0] * (W + 1)
for i in range(n):
for w in range(W, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
weights = [10, 20, 30]
values = [60, 100, 120]
W = 50
print(knapsack_space_optimized(weights, values, W))
easy
A. 240
B. 180
C. 160
D. 220
Solution
Step 1: Trace dp array updates for each item
For item 0 (weight=10, value=60), dp[w] updated for w=50 down to 10, dp[10..50]=60. For item 1 (weight=20, value=100), dp[30]=max(dp[30], dp[10]+100)=160, dp[50]=max(dp[50], dp[30]+100)=220. For item 2 (weight=30, value=120), dp[50]=max(dp[50], dp[20]+120)=max(220, 160+120)=280 but dp[20] is 60, so dp[50]=max(220, 180)=220.
Step 2: Final dp[50] value
The maximum value achievable with capacity 50 is 220.
Final Answer:
Option D -> Option D
Quick Check:
Manual dp tracing confirms max value 220 [OK]
Hint: Trace dp updates backward to avoid overcounting [OK]
Common Mistakes:
Forwards iteration over w causes overcounting items.
2. Consider the following Python code for the Equal Partition problem. What is the value of dp[target] after processing the input [1, 5, 11, 5]?
def canPartition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for w in range(target, num - 1, -1):
dp[w] = dp[w] or dp[w - num]
return dp[target]
print(canPartition([1,5,11,5]))
easy
A. true
B. false
C. null (error occurs)
D. Depends on order of iteration
Solution
Step 1: Calculate total and target
The total sum is 1 + 5 + 11 + 5 = 22, which is even, so target = 11.
Step 2: Trace dp array updates for each num
After processing all nums, dp[11] becomes True because subset {11} or {5,5,1} sums to 11.
Final Answer:
Option A -> Option A
Quick Check:
Input is classic example where partition exists; dp[target] is True [OK]
Hint: Sum is even and dp[target] tracks subset sums [OK]
Common Mistakes:
Confusing dp[target] with dp[target-1]
Forgetting to iterate backwards in dp update
3. What is the time complexity of the bottom-up dynamic programming solution for the integer break problem shown below?
def integer_break(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
max_product = 0
for j in range(1, i):
max_product = max(max_product, max(j, dp[j]) * max(i - j, dp[i - j]))
dp[i] = max_product
return dp[n]
medium
A. O(n log n) time
B. O(n) time
C. O(2^n) time
D. O(n^2) time
Solution
Step 1: Identify loops
Outer loop runs from 2 to n (≈ n iterations). Inner loop runs from 1 to i (up to n iterations).
Double nested loops with linear bounds -> quadratic time [OK]
Hint: Nested loops with linear bounds usually mean O(n²) [OK]
Common Mistakes:
Confusing with O(n) by ignoring inner loop
Thinking recursion stack adds exponential time here
4. What is the time complexity of the bottom-up dynamic programming solution for the Perfect Squares problem using the unbounded knapsack pattern, where n is the input number?
medium
A. O(n^2)
B. O(sqrt(n) * log n)
C. O(n * log n)
D. O(n * sqrt(n))
Solution
Step 1: Identify loops in the algorithm
The outer loop runs from 1 to n (O(n)). The inner loop iterates over all perfect squares less than or equal to i, which is approximately O(sqrt(n)) because the largest square root is about sqrt(n).
Step 2: Combine complexities
Multiplying outer and inner loops gives O(n * sqrt(n)). Other options either overestimate (O(n^2)) or underestimate (O(n log n), O(sqrt(n) log n)) the complexity.
Final Answer:
Option D -> Option D
Quick Check:
Nested loops: n and sqrt(n) -> O(n * sqrt(n)) [OK]
Hint: Inner loop runs up to sqrt(n), outer up to n [OK]
Common Mistakes:
Assuming inner loop is O(n)
Confusing recursion stack space with DP space
5. The following code attempts to solve the subset sum problem using space-optimized DP. Identify the bug that causes incorrect results on some inputs.
medium
A. Line 2: dp[0] should be initialized to False
B. Line 6: dp[w] should be assigned dp[w - num] only, not ORed
C. Line 4: The outer loop should iterate backwards over nums
D. Line 5: The inner loop iterates forwards instead of backwards
Solution
Step 1: Understand dp update direction
Iterating forwards causes dp[w] to use updated dp[w - num] from the same iteration, leading to overcounting.
Step 2: Correct iteration direction
Iterating backwards ensures dp[w - num] is from previous iteration, preserving correctness.
Final Answer:
Option D -> Option D
Quick Check:
Forward iteration breaks subset sum correctness -> bug at line 5 [OK]
Hint: DP must iterate sums backward to avoid reuse in same iteration [OK]
Common Mistakes:
Initializing dp[0] incorrectly
Misusing OR in dp update
Wrong loop order over nums
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.