Maximum Profit in Job Scheduling
Problem statement
You are given equal-length arrays startTime, endTime, and profit. Job i runs on the half-open interval from its start time to its end time and earns its profit.
Select non-overlapping jobs to maximize total profit. A job that starts exactly when another ends does not overlap.
Function
jobScheduling(startTime: int[], endTime: int[], profit: int[]) → intExamples
Example 1
startTime = [1,2,3,3]endTime = [3,4,5,6]profit = [50,10,40,70]return = 120Choose jobs [1,3) and [3,6) for profit 120.
Example 2
startTime = [1,2,3,4,6]endTime = [3,5,10,6,9]profit = [20,20,100,70,60]return = 150Jobs [1,3), [4,6), and [6,9) earn 150.
Example 3
startTime = [1,1,1]endTime = [2,3,4]profit = [5,6,4]return = 6All jobs overlap, so choose the highest-profit one.
Constraints
1 ≤ startTime.length = endTime.length = profit.length ≤ 50000.0 ≤ startTime[i] < endTime[i] ≤ 10^9.1 ≤ profit[i] ≤ 10000.