518. Weighted Job Scheduling (Binary Search + DP)

Given jobs each described by [start, end, profit], where no two scheduled jobs may overlap in time (a job ending at time t does not conflict with a job starting at t), return the maximum total profit obtainable. Sort by end time and use binary search inside a DP. Input: a JSON array of [start, end, profit].

Input: A JSON array of [start, end, profit].

Output: Integer — the maximum profit.

Examples

Input: [[1,3,50],[3,5,20],[6,19,100],[2,100,200]]
Output: 200
Explanation: The single long job yields the most.

Input: [[1,2,50],[3,4,60],[6,7,70]]
Output: 180
Explanation: All three fit.

Input: [[1,2,5]]
Output: 5
Explanation: Single job.

Constraints

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

Asked by