556. Maximum Profit in Job Scheduling (Binary Search + DP)

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

Input: A JSON array of [startTime, endTime, 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 is best.

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