Maximum Profit in Job Scheduling

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i]. Return the maximum profit you can take such that there are no two jobs with overlapping time ranges.

30:00

Maximum Profit in Job Scheduling

hard

Topics

Companies

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i]. Return the maximum profit you can take such that there are no two jobs with overlapping time ranges.

Example 1:

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

Output: 120

Constraints:

$1 \leq \text{startTime.length} == \text{endTime.length} == \text{profit.length} \leq 5 \times 10^4$
$1 \leq \text{startTime}[i] < \text{endTime}[i] \leq 10^9$
$1 \leq \text{profit}[i] \leq 10^4$

Input

arr ={"startTime":[1,2,3,3],"endTime":[3,4,5,6],"profit":[50,10,40,70]}

4 jobs, sorted by start time. Solve from the last job backwards: dp[i] is the best profit available from job i onwards.

State

jobs

[[object Object], [object Object], [object Object], [object Object]]

n

4

span

6

dp

[0, 0, 0, 0, 0]

i

-1

Variables

n=4

Variables

Variable	Value
n	4

DepthFunction Call

Stack empty

0/15