1207. Weighted Job Scheduling (DP + Binary Search)

Given jobs as [start, end, profit], select non-overlapping jobs (a job starting exactly when another ends is allowed) to maximize total profit. Return that maximum profit. The input is JSON {jobs}.

Input: JSON {jobs}.

Output: Integer — the maximum total profit.

Examples

Input: {"jobs":[[1,2,50],[3,5,20],[6,19,100],[2,100,200]]}
Output: 250
Explanation: Take [1,2,50] and [2,100,200].

Input: {"jobs":[[1,3,10]]}
Output: 10
Explanation: Single job.

Input: {"jobs":[[1,2,5],[2,3,6]]}
Output: 11
Explanation: Both jobs fit.

Constraints

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

Asked by