Bird
Raised Fist0
Interview Prepdp-knapsackhardAmazonGoogleFacebook

Maximum Profit in Job Scheduling

Choose your preparation mode4 modes available
📋
Problem

Imagine you are a freelancer with multiple job offers, each with a start time, end time, and profit. You want to schedule jobs to maximize your total earnings without overlapping any jobs.

Given n jobs where every job is represented as (startTime, endTime, profit), find the maximum profit you can earn by scheduling non-overlapping jobs. You may choose to skip some jobs. Return the maximum profit achievable.

1 ≤ n ≤ 10^51 ≤ startTime[i], endTime[i], profit[i] ≤ 10^9startTime[i] < endTime[i]
Edge cases: All jobs overlap completely → output is max single job profitJobs with same start and end times but different profits → pick highest profit jobJobs sorted in descending order of end time → algorithm must still work
</>
IDE
def jobScheduling(startTime: List[int], endTime: List[int], profit: List[int]) -> int:public int jobScheduling(int[] startTime, int[] endTime, int[] profit)int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit)function jobScheduling(startTime, endTime, profit)
def jobScheduling(startTime, endTime, profit):
    # Write your solution here
    pass
class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
    // Write your solution here
    return 0;
}
function jobScheduling(startTime, endTime, profit) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: Less than max profit due to greedy scheduling by earliest end timeUsing greedy approach instead of DP with binary search for last non-conflicting job✅ Implement DP recurrence dp[i] = max(dp[i-1], profit[i] + dp[last_non_conflict]) with binary search to find last non-conflicting job
Wrong: Sum of all profits ignoring overlapsNot enforcing non-overlapping constraint in DP or binary search✅ Ensure binary search finds last job that ends before current job starts and add dp[last_non_conflict] only if no overlap
Wrong: Incorrect result due to unsorted jobsNot sorting jobs by end time before DP and binary search✅ Sort jobs by end time before processing and binary searching
Wrong: Crash or wrong output on empty inputNo base case handling for empty input arrays✅ Add base case: if no jobs, return 0 immediately
Wrong: Wrong profit for single job inputDP initialization incorrect for single element✅ Initialize dp[0] = profit[0] for single job input
✓
Test Cases
t1_01basic
Input{"startTime":[1,2,3,4,6],"endTime":[3,5,10,6,9],"profit":[20,20,100,70,60]}
Expected150

Schedule jobs 1 (1-3, profit 20), 4 (4-6, profit 70), and 5 (6-9, profit 60) for total 150.

t1_02basic
Input{"startTime":[1,3,3,5,6],"endTime":[2,4,6,7,9],"profit":[50,10,40,70,60]}
Expected150

Schedule jobs 1 (1-2, 50), 4 (5-7, 70), and 5 (6-9, 60) overlap but job 4 and 5 overlap, so best is jobs 1,3,5 for total 150.

t2_01edge
Input{"startTime":[],"endTime":[],"profit":[]}
Expected0

Empty input means no jobs to schedule, so max profit is 0.

t2_02edge
Input{"startTime":[1],"endTime":[2],"profit":[100]}
Expected100

Single job can be scheduled alone for profit 100.

t2_03edge
Input{"startTime":[1,1,1],"endTime":[2,2,2],"profit":[10,50,20]}
Expected50

All jobs overlap completely; pick job with max profit 50.

t3_01corner
Input{"startTime":[1,2,3,4],"endTime":[3,5,10,6],"profit":[20,20,100,70]}
Expected120

Greedy approach picking jobs by earliest end time fails; correct is jobs 1 and 4 for total 90 or jobs 3 alone for 100, but best is jobs 1 and 4 for 90 or job 3 alone 100; actually jobs 1 and 4 overlap? Jobs 1(1-3), 4(4-6) no overlap, total 90; job 3 alone 100; best is 100.

t3_02corner
Input{"startTime":[1,2,3,4,5],"endTime":[2,3,4,5,6],"profit":[10,20,30,40,50]}
Expected90

Jobs are continuous intervals; only one job can be chosen at a time; best is jobs 1,3,5 for total 10+30+50=90.

t3_03corner
Input{"startTime":[5,1,3,4,2],"endTime":[6,2,5,7,4],"profit":[50,20,100,70,60]}
Expected150

Jobs unsorted by end time; algorithm must sort and still find max profit 150 by scheduling jobs 2,4,5.

t4_01performance
Input{"_description":"n=100000 at constraint boundary - executor generates this input"}
⏱ Performance - must finish in 2000ms

Test with 100000 jobs to verify O(n log n) DP with binary search completes within 2 seconds.

Practice

(1/5)
1. You need to find the minimum number of perfect square numbers that sum to a given integer n. Which algorithmic approach guarantees an optimal solution for this problem?
easy
A. Dynamic programming using unbounded knapsack pattern with bottom-up tabulation
B. Greedy approach picking the largest square first until the sum is reached
C. Simple recursion without memoization exploring all combinations
D. Sorting all squares and using binary search to find the closest sum

Solution

  1. Step 1: Understand problem constraints

    The problem requires the minimum count of perfect squares summing to n, which is a classic unbounded knapsack variant where items (squares) can be reused.
  2. Step 2: Identify algorithm that guarantees optimality

    Greedy fails because picking largest squares first can be suboptimal (e.g., n=12). Simple recursion is correct but inefficient. Binary search does not solve the combinatorial optimization. Bottom-up DP with unbounded knapsack pattern systematically explores all combinations and ensures optimality.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    DP approach always finds minimum count [OK]
Hint: Greedy fails; DP unbounded knapsack guarantees optimal [OK]
Common Mistakes:
  • Assuming greedy works for minimum perfect squares
  • Confusing top-down recursion with guaranteed efficiency
2. The following code attempts to solve the integer break problem using bottom-up DP. Which line contains a subtle bug that can cause incorrect results on some inputs?
def integer_break(n):
    dp = [0] * n
    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. Line 3: dp[1] = 1 base case initialization
B. Line 2: dp array size is n instead of n+1
C. Line 5: Outer loop range from 2 to n+1
D. Line 7: Using max(j, dp[j]) instead of just dp[j]

Solution

  1. Step 1: Check dp array size

    dp is initialized with size n, but indices up to n are accessed (dp[i], dp[i-j]) which requires size n+1.
  2. Step 2: Consequences of wrong size

    Accessing dp[n] or dp[i-j] when i=n causes index out of range or incorrect results.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    dp array must be size n+1 to safely index up to n [OK]
Hint: Check array size matches max index accessed [OK]
Common Mistakes:
  • Forgetting dp size off-by-one
  • Misplacing base case initialization
3. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the minimum subset sum difference problem, given an input array of size n and total sum S?
medium
A. O(S^2)
B. O(n^2)
C. O(n * S)
D. O(n * log S)

Solution

  1. Step 1: Identify loops in the code

    Outer loop runs n times (for each element), inner loop runs up to total_sum S times.
  2. Step 2: Calculate total complexity

    Time complexity is O(n * S) because each element updates dp array of size S.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    DP iterates over n elements and sums up to S [OK]
Hint: Time depends on n and total sum, not n squared [OK]
Common Mistakes:
  • Confusing n with S or assuming quadratic n^2
  • Ignoring dp array size impact
4. What is the time complexity of the DP with bitmask tabulation approach for partitioning an array of size n into k equal sum subsets, where the algorithm iterates over all subsets and elements?
medium
A. O(k^n) because it tries all assignments of elements to k buckets
B. O(n * 2^n) because it iterates over all subsets and elements
C. O(n * target) where target is the subset sum
D. O(2^n * n^2) due to nested loops over subsets and elements

Solution

  1. Step 1: Identify loops in the algorithm

    The outer loop iterates over all subsets (2^n), inner loop over n elements.
  2. Step 2: Calculate total complexity

    Combining loops gives O(n * 2^n). The target sum does not affect iteration count directly.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    DP bitmask iterates all subsets and elements [OK]
Hint: Bitmask DP complexity is n times 2^n subsets [OK]
Common Mistakes:
  • Confusing brute force backtracking complexity with DP complexity
  • Assuming complexity depends on target sum
5. The following code attempts to compute the minimum number of perfect squares summing to n. Which line contains a subtle bug that can cause incorrect results or infinite loops?
medium
A. Line 3: Missing base case assignment dp[0] = 0
B. Line 2: dp initialization with infinity
C. Line 5: Outer loop from 1 to n
D. Line 7: Inner loop condition j*j <= i

Solution

  1. Step 1: Identify base case importance

    dp[0] = 0 is critical because it represents zero squares needed to sum to zero. Without it, dp[0] remains infinity, causing dp[i] updates to use invalid values.
  2. Step 2: Analyze impact of missing dp[0] = 0

    Since dp[0] is infinity, expressions like 1 + dp[i - j*j] become infinity, preventing dp[i] from ever updating correctly, leading to infinite loops or wrong results.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Missing dp[0] base case breaks DP initialization [OK]
Hint: dp[0] must be zero to start DP correctly [OK]
Common Mistakes:
  • Forgetting dp[0] initialization
  • Misplacing loop boundaries
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