Skip to main content

1235. Maximum Profit in Job Scheduling

hard

Pick non-overlapping jobs to maximize profit. Sort by end time, then DP with binary search to skip back to the last compatible job in O(n log n).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i]. You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range. If you choose a job that ends at time X you will be able to start another job that starts at time X.

Constraints

  • 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
  • 1 <= startTime[i] < endTime[i] <= 10^9
  • 1 <= profit[i] <= 10^4

Examples

Example 1

Input
startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output
120

Explanation: The subset chosen is the first and fourth job. Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2

Input
startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output
150

Explanation: The subset chosen is the first, fourth and fifth job. Profit obtained 150 = 20 + 70 + 60.

Example 3

Input
startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output
6

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Sort jobs by endTime ascending. Now decisions are 'include job i' or 'skip job i'.

Hint 2

dp[i] = max profit using only the first i jobs (in sorted order). Recurrence: dp[i] = max(dp[i-1], profit[i] + dp[j]) where j is the latest job whose endTime <= startTime[i].

Hint 3

Binary search for j in the sorted endTime array. Total O(n log n).

Solution approach

Reveal approach

Sort jobs by end time ascending. Build dp[0..n] where dp[i] is the maximum profit considering only the first i sorted jobs. dp[0] = 0. For each i from 1 to n, two options: skip the i-th job (dp[i] = dp[i-1]) or take it (dp[i] = profit[i] + dp[j]) where j is the count of jobs whose end time is at most the i-th job's start time. Binary search for j in the sorted end-time list. dp[i] is the max of the two. Return dp[n]. O(n log n) time, O(n) space. The binary search is the key — without it the inner loop makes it O(n^2).

Complexity

Time
O(n log n)
Space
O(n)

Related patterns

  • dynamic-programming
  • binary-search
  • sorting
  • weighted-interval-scheduling

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Facebook

Practice these live with InterviewChamp.AI

Drill Maximum Profit in Job Scheduling and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →