1208. Maximum Profit in Job Scheduling

Given parallel arrays startTime, endTime, and profit describing jobs, select non-overlapping jobs (a job may start exactly when another ends) to maximize total profit. Return that maximum profit. The input is JSON {startTime, endTime, profit}.

Input: JSON {startTime, endTime, profit}.

Output: Integer — the maximum total profit.

Examples

Input: {"startTime":[1,2,3,3],"endTime":[3,4,5,6],"profit":[50,10,40,70]}
Output: 120
Explanation: Take the first and last jobs.

Input: {"startTime":[1,2,3,4,6],"endTime":[3,5,10,6,9],"profit":[20,20,100,70,60]}
Output: 150
Explanation: An optimal non-overlapping set.

Input: {"startTime":[1],"endTime":[2],"profit":[5]}
Output: 5
Explanation: Single job.

Constraints

• 1<=n<=5*10^4

Asked by