Weighted Job Scheduling

Each job is [start, end, profit] with start < end. You can do one job at a time; a job that ends at time t does not overlap one that starts at t. Return the largest total profit from a set of non-overlapping jobs.

For [[1, 3, 50], [2, 4, 10], [3, 5, 40], [3, 6, 70]] the answer is 120 (jobs 1 and 4).

The starter code scans backwards through all earlier jobs for each job. It is correct but too slow for many jobs.

Examples

Example 1

Input:

job_scheduling([[1, 3, 50], [2, 4, 10], [3, 5, 40], [3, 6, 70]])

Output:

120

Example 2

Input:

job_scheduling([[1, 2, 5], [1, 2, 6]])

Output:

6

Constraints

• 0 <= len(jobs) <= 100000
• 1 <= start < end <= 10**9
• 1 <= profit <= 10000