Maximum Profit in Job Scheduling
You are given n jobs described with three arrays: startTime, endTime, and profit. The i--th job starts at startTime[i], ends at endTime[i], and yields a profit of profit[i].
Return the maximum profit achievable by selecting a subset of jobs such that no two selected jobs overlap in their time ranges.
Note: If a job ends at time X, you are allowed to start another job that begins exactly at time X.
Example 1:
Input: startTime = [4,2,4,8,2], endTime = [5,5,5,10,8], profit = [1,2,8,10,4]
Output: 18Explanation: The subset to choose to get maximum profit is the third and fourth job (8 + 10 = 18).
Example 2:
Input: startTime = [2,3,4,5,7], endTime = [4,6,11,7,10], profit = [100,100,180,150,140]
Output: 390Explanation: The subset to choose to get maximum profit is the first, second and fifth job (100 + 140 + 150 = 390).
Constraints:
1 <= startTime.length == endTime.length == profit.length <= 50,0001 <= startTime[i] < endTime[i] <= 1,000,000,0001 <= profit[i] <= 10,000