Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Maximum Profit in Job Scheduling

LeetCode #1235Hard
Sort by end; take or skip

Given jobs each with a start time, end time, and profit, choose a subset of non-overlapping jobs that maximizes total profit and return that maximum.

Asked atAmazonGoogle
step 1 / 11
50
10
40
70
[0][1][2][3]
dp
·
·
·
·
[0][1][2][3]
DP after sorting by end time
▸
1sort jobs by end time
2dp = array of size n
3for i in 0..n−1:
4    p = latest j with end[j] <= start[i]   // binary search
5    skip = dp[i−1]                          // (0 if i==0)
6    take = profit[i] + (p>=0 ? dp[p] : 0)
7    dp[i] = max(skip, take)
8return dp[n−1]
state
  • jobs (by end)job0 [1,3] $50 job1 [2,4] $10 job2 [3,5] $40 job3 [3,6] $70
  • recurrencedp[i] = max(dp[i−1], profit[i] + dp[p(i)])

line 1Maximum Profit in Job Scheduling: each job has a start, an end, and a profit, and two jobs clash if their time ranges overlap. Pick a non-overlapping subset with the greatest total profit. The main row shows each job by its profit; the start/end live in the State panel. The key move is to SORT jobs by END time.