Maximum Profit in Job Scheduling

You are given n jobs where every job is represented by three arrays: startTime, endTime, and profit.

The ith job starts at startTime[i], ends at endTime[i], and yields profit[i].

You may pick a subset of non-overlapping jobs to maximize total profit. If a job ends at time x, another job starting at time x can be selected.

Return the maximum profit you can achieve.

Examples

Example 1:

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

Output: 120

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]

Output: 150

Constraints

• 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
• 1 <= startTime[i] < endTime[i] <= 10^9
• 1 <= profit[i] <= 10^4