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 ```python 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** ```text 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** ```text 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.