Choose Non-Overlapping Weighted Jobs to Maximize Total Profit
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Overview: Choose a set of jobs, each with a start time, end time and profit, so that no two chosen jobs overlap and the total profit is as large as possible. It tests sorting intervals, defining an optimal-substructure recurrence, and finding the latest compatible earlier job efficiently for large inputs.
Read the full Google Software Engineer interview experience this question came from
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.
Implement `max_profit(start_time, end_time, profit)`. The three lists have the same length `n`, and position `i` of each list describes job `i`. Return a single integer: the largest total profit. Only this value is returned, not the chosen jobs, so the answer is unique even when several sets of jobs tie.
### 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.
No input value or answer exceeds `2^31 - 1`, so a 32-bit `int` is sufficient in Java and C++.
### 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.
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
Input: ([1, 2, 4, 6, 5], [4, 6, 7, 9, 8], [20, 30, 25, 15, 40])
Expected Output: 60
Explanation: Source Example 1: [1, 4) plus [5, 8) earns 60; earliest-end greedy stops at 45.
Input: ([1, 3, 2], [3, 5, 4], [5, 6, 10])
Expected Output: 11
Explanation: Source Example 2: touching jobs [1, 3) and [3, 5) beat the single most profitable job [2, 4).
Hints
- Two jobs are compatible exactly when one ends at or before the moment the other starts; a shared endpoint is allowed.
- Neither always taking the most profitable remaining job nor always taking the job that finishes first is safe: Example 2 defeats the first rule and Example 1 defeats the second.
- The input order is arbitrary, so choose an order to process the jobs in that makes it easy to tell, for each job, which jobs could come before it in a schedule.