Highest Total Profit from Non-Overlapping Jobs When Endpoints May Touch

Each job has a start time, an end time and a profit. Choose jobs that do not overlap in time so that the total profit is as large as possible.

Function Signature

def max_job_profit(jobs: list[list[int]]) -> int:

Rules

• jobs[i] = [start, end, profit] means job i occupies the time from start up to end.
• No two chosen jobs may overlap. A job that ends at time t and a job that starts at time t do not overlap, so both can be chosen.
• Any number of jobs can be chosen. Return the largest possible total profit.

Constraints

• 1 <= len(jobs) <= 5 * 10^4
• 1 <= start < end <= 10^9 for every job
• 1 <= profit <= 10^4 for every job, so the answer is at most 5 * 10^8.

Examples

Example 1

Input: jobs = [[1, 4, 20], [2, 6, 30], [4, 7, 25], [7, 9, 15]]
Output: 60

The jobs [1, 4], [4, 7] and [7, 9] touch end to start, for 20 + 25 + 15 = 60. The profit-30 job overlaps the first two and, combined with [7, 9], gives only 45.

Example 2

Input: jobs = [[1, 2, 5], [1, 3, 6], [2, 3, 4]]
Output: 9

The jobs [1, 2] and [2, 3] give 9, more than [1, 3] alone.

Example 3

Input: jobs = [[1, 10, 100], [2, 3, 30], [3, 4, 30], [4, 5, 30]]
Output: 100

The three short jobs together give only 90.