> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Maximum Profit in Job Scheduling

> Tested Python solution for LeetCode 1235 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 1235, Hard. Topics: Array, Binary Search, Dynamic Programming, Sorting. [View on LeetCode](https://leetcode.com/problems/maximum-profit-in-job-scheduling/description/).

Generate this problem as a practice environment: tested reference solution, 12 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1235   # by problem number
lcpy gen -s maximum_profit_in_job_scheduling   # by problem name
```

## Problem

We have `n` jobs, where every job is scheduled to be done from `startTime[i]` to `endTime[i]`, obtaining a profit of `profit[i]`.

You're given the `startTime`, `endTime` and `profit` arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time `X` you will be able to start another job that starts at time `X`.

### Examples

![Example 1](https://assets.leetcode.com/uploads/2019/10/10/sample1_1584.png)

```
Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
Output: 120
```

**Explanation:** The subset chosen is the first and fourth job. Time range \[1-3]+\[3-6] , we get profit of 120 = 50 + 70.

![Example 2](https://assets.leetcode.com/uploads/2019/10/10/sample22_1584.png)

```
Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
Output: 150
```

**Explanation:** The subset chosen is the first, fourth and fifth job. Profit obtained 150 = 20 + 70 + 60.

![Example 3](https://assets.leetcode.com/uploads/2019/10/10/sample3_1584.png)

```
Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
Output: 6
```

### Constraints

* `1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4`
* `1 <= startTime[i] < endTime[i] <= 10^9`
* `1 <= profit[i] <= 10^4`

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_profit_in_job_scheduling/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_profit_in_job_scheduling/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import bisect


class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def job_scheduling(self, start_time: list[int], end_time: list[int], profit: list[int]) -> int:
        jobs = sorted(zip(end_time, start_time, profit, strict=False))
        dp = [0] * len(jobs)

        for i, (_end, start, p) in enumerate(jobs):
            # Binary search for latest non-overlapping job
            j = bisect.bisect_right([job[0] for job in jobs[:i]], start) - 1

            # Take current job + best profit from non-overlapping jobs
            take = p + (dp[j] if j >= 0 else 0)
            # Skip current job
            skip = dp[i - 1] if i > 0 else 0

            dp[i] = max(take, skip)

        return dp[-1] if jobs else 0


# bisect and insort Explanation:
#
# Etymology: "bisect" = bi (two) + sect (cut) = cut into two parts
# Bisection method = binary search algorithm that repeatedly cuts search space in half
#
# bisect module provides binary search for SORTED lists (O(log n)):
# - bisect_left(arr, x): leftmost insertion position
# - bisect_right(arr, x): rightmost insertion position (default)
# - bisect(arr, x): alias for bisect_right
#
# insort module maintains sorted order while inserting:
# - insort_left(arr, x): insert at leftmost position
# - insort_right(arr, x): insert at rightmost position (default)
# - insort(arr, x): alias for insort_right
#
# Examples:
# arr = [1, 3, 3, 5]
# bisect_left(arr, 3) → 1   (before existing 3s)
# bisect_right(arr, 3) → 3  (after existing 3s)
# bisect_right(arr, 4) → 3  (between 3 and 5)
#
# insort(arr, 4) → arr becomes [1, 3, 3, 4, 5]
#
# In our solution:
# bisect_right([2,4,6], 5) = 2 (insertion position)
# j = 2 - 1 = 1 (index of latest job ending ≤ start_time)
```

## Complexity

| Time       | Space |
| ---------- | ----- |
| O(n log n) | O(n)  |

## Tags

[Grind 75](/catalog/grind-75), [Grind](/catalog/grind), [NeetCode All](/catalog/neetcode).