Highest Total Profit from Non-Overlapping Jobs When Endpoints May Touch
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
Input: jobs = [[1, 10, 100], [2, 3, 30], [3, 4, 30], [4, 5, 30]]
Output: 100
```
The three short jobs together give only 90.
Overview: Each job has a start time, an end time and a profit; choose jobs that do not overlap, where one job may start exactly when another ends, to maximize the total profit. It tests weighted interval scheduling and handling touching endpoints correctly.
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.
Implement `max_job_profit(jobs)`, where `jobs[i] = [start, end, profit]` means job `i` occupies the time from `start` up to `end` and earns `profit` if chosen.
### Rules
- 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 as an integer.
- `jobs` is not necessarily sorted, and it may contain identical jobs.
### 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`. Every value, including the answer, fits in a signed 32-bit integer.
### Example 1
```text
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
```text
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.
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; every value, including the answer, fits in a signed 32-bit integer
Examples
Input: ([[1, 4, 20], [2, 6, 30], [4, 7, 25], [7, 9, 15]],)
Expected Output: 60
Explanation: Source Example 1: the touching chain [1,4], [4,7], [7,9] gives 20 + 25 + 15; taking the profit-30 job first gives only 45.
Input: ([[1, 2, 5], [1, 3, 6], [2, 3, 4]],)
Expected Output: 9
Explanation: Source Example 2: [1,2] and [2,3] touch for 9, beating the single most profitable job (6), so greedy by highest profit fails.
Hints
- A job that ends at time t and a job that starts at time t are compatible, so make sure your overlap test treats touching jobs as non-overlapping.
- Simple greedy rules fail: in Example 2, always grabbing the most profitable job gives only 6, and a single long job can be worth more than the several short jobs it covers, so always grabbing the job that ends first fails too.
- The input is unsorted and times reach 10^9, so anything indexed by individual time units is far too large; only the jobs' own start and end times matter.