Choose Non-Overlapping Weighted Jobs to Maximize Total Profit

You are given n jobs. Job i starts at start_time[i], ends at end_time[i], and earns profit[i] if you take it. You may take any set of jobs as long as no two of them overlap in time. Return the largest total profit you can earn.

Function Signature

def max_profit(start_time: list[int], end_time: list[int], profit: list[int]) -> int:

Rules

• Job i occupies the half-open time interval [start_time[i], end_time[i]). Two jobs overlap when their intervals share any time, so a job that ends at time x and a job that starts at time x can both be taken.
• The jobs are given in no particular order.

Constraints

• 1 <= n <= 100000, with len(start_time) == len(end_time) == len(profit) == n
• 1 <= start_time[i] < end_time[i] <= 10^9
• 1 <= profit[i] <= 10^4
• The total profit is at most 10^9, which fits in a 32-bit signed integer.

Examples

Example 1

Input: start_time = [1, 2, 4, 6, 5]
 end_time = [4, 6, 7, 9, 8]
 profit = [20, 30, 25, 15, 40]
Output: 60

Take the job [1, 4) (profit 20) and the job [5, 8) (profit 40). No other compatible set earns more; for example, [2, 6) with [6, 9) earns 45.

Example 2

Input: start_time = [1, 3, 2]
 end_time = [3, 5, 4]
 profit = [5, 6, 10]
Output: 11

[1, 3) and [3, 5) touch at time 3 but do not overlap, so both can be taken for 11, which beats the single job [2, 4) worth 10.