Maximum Profit from Non-Overlapping Jobs
Problem statement
Job i starts at startTime[i], ends at endTime[i], and earns profit[i]. Choose a subset of non-overlapping jobs with maximum total profit.
A job that starts exactly when another selected job ends does not overlap it.
Function
maximumJobProfit(startTime: int[], endTime: int[], profit: int[]) → longExamples
Example 1
startTime = [1,2,3,3]endTime = [3,4,5,6]profit = [50,10,40,70]return = 120Select jobs [1,3] and [3,6].
Example 2
startTime = [1,2,3,4,6]endTime = [3,5,10,6,9]profit = [20,20,100,70,60]return = 150The jobs spanning [1,3], [4,6], and [6,9] earn 150.
Example 3
startTime = [1]endTime = [2]profit = [7]return = 7The only job is selected.
Constraints
1 <= startTime.length == endTime.length == profit.length <= 100000.1 <= startTime[i] < endTime[i] <= 10^9.1 <= profit[i] <= 10^9.