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.

Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

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

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.

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.

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, full suite in test_solution.py:

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, Grind, NeetCode All.