Bird
Raised Fist0
Interview Prepdp-knapsackhardAmazonGoogleFacebook

Maximum Profit in Job Scheduling

Choose your preparation mode4 modes available
▶
Steps
setup

Sort jobs by end time

Jobs are sorted by their end times to process them in chronological order of completion.

💡 Sorting by end time ensures we consider jobs in a way that respects scheduling constraints.
Line:jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])
💡 Sorting is crucial to efficiently find compatible jobs later.
📊
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\w01234
i=0?????
Job 1 (1,3,20)
Initializing dp array
i\w01234
i=0?????
dp unfilled
Item 0 - wt:3 val:20
i\w01234
i=020????
dp[0] = 20 (take job 0)
Item 1 - wt:5 val:20
i\w01234
i=02020???
dp[1] = 20 (skip or take job 1)
Item 2 - wt:6 val:70
i\w01234
i=0202090??
dp[2] = 90 (take job 2 + dp[0])
Item 3 - wt:9 val:60
i\w01234
i=0202090??
Compatible job idx = 2
Item 3 - wt:9 val:60
i\w01234
i=0202090150?
dp[3] = 150 (take job 3 + dp[2])
Item 4 - wt:10 val:100
i\w01234
i=0202090150?
Compatible job idx = 0
Item 4 - wt:10 val:100
i\w01234
i=0202090150150
dp[4] = 150 (skip job 4)
Item 4 - wt:10 val:100
i\w01234
i=0202090150150
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

  1. 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.
  2. Step 2: Final dp[50] value

    The maximum value achievable with capacity 50 is 220.
  3. Final Answer:

    Option D -> Option D
  4. 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

  1. Step 1: Calculate total and target

    The total sum is 1 + 5 + 11 + 5 = 22, which is even, so target = 11.
  2. 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.
  3. Final Answer:

    Option A -> Option A
  4. 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

  1. Step 1: Identify loops

    Outer loop runs from 2 to n (≈ n iterations). Inner loop runs from 1 to i (up to n iterations).
  2. Step 2: Calculate total operations

    Nested loops yield roughly 1 + 2 + ... + n ≈ n(n+1)/2 = O(n^2) operations.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    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

  1. 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).
  2. 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.
  3. Final Answer:

    Option D -> Option D
  4. 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

  1. Step 1: Understand dp update direction

    Iterating forwards causes dp[w] to use updated dp[w - num] from the same iteration, leading to overcounting.
  2. Step 2: Correct iteration direction

    Iterating backwards ensures dp[w - num] is from previous iteration, preserving correctness.
  3. Final Answer:

    Option D -> Option D
  4. 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 unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard