#1235

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Profit in Job Scheduling

Compute the maximum profit from non-overlapping jobs using state transition dynamic programming with sorted arrays and binary search.

array binary search dynamic programming sorting

Problem Statement

You are given three arrays startTime, endTime, and profit, each of length n, representing n jobs. Job i starts at startTime[i], ends at endTime[i], and yields a profit of profit[i]. Your task is to select a subset of jobs to maximize total profit such that no two selected jobs overlap in time. If a job ends at time X, another job starting at X can be included.

Return the maximum total profit obtainable under these constraints. Optimize your approach using state transition dynamic programming, considering that naive iteration over all subsets is too slow for large n.

Examples

Example 1

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

Output: 120

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

Example 2

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

Output: 150

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

Example 3

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

Output: 6

Example details omitted.

Constraints

1 <= startTime.length == endTime.length == profit.length <= 5 * 104
1 <= startTime[i] < endTime[i] <= 109
1 <= profit[i] <= 104

Solution Approach

Sort Jobs by End Time

First, combine the startTime, endTime, and profit arrays into a list of job tuples. Sort this list by endTime to allow efficient lookups of the last non-overlapping job for each job using binary search.

Dynamic Programming State Transition

Initialize a DP array where dp[i] represents the maximum profit including jobs up to index i. For each job, perform a binary search to find the latest job that ends before the current job starts. Update dp[i] as the maximum of dp[i-1] (skipping current job) and dp[lastCompatible] + profit[i] (including current job).

Binary Search for Compatible Jobs

Use binary search to efficiently locate the last job that finishes before the current job starts. This avoids linear scans and maintains the overall time complexity near O(n log n). Each DP update then considers only valid non-overlapping sequences.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) due to sorting and binary search for each job. Space complexity is O(n) for storing DP states and the combined job list.

What Interviewers Usually Probe

Expect sorting by end times before DP.
Look for correct DP state definition to store maximum profit up to each job.
Binary search for previous compatible job is crucial for efficiency.

Common Pitfalls or Variants

Common pitfalls

Forgetting that a job ending at X can allow a new job starting at X.
Performing linear search instead of binary search, increasing runtime.
Incorrectly updating DP array, not considering the maximum between including or skipping a job.

Follow-up variants

Allow jobs with equal start and end times and handle them in DP updates.
Find the maximum number of jobs instead of profit using a similar DP approach.
Add a constraint on maximum total duration and adapt the DP to track both profit and duration.

FAQ

What is the main approach to solve Maximum Profit in Job Scheduling?

Use state transition dynamic programming with jobs sorted by end time and binary search to find the latest non-overlapping job for each step.

Can jobs that end and start at the same time be scheduled together?

Yes, a job ending at time X allows inclusion of another job starting at X without overlapping.

What is the time complexity for this DP with binary search approach?

Sorting takes O(n log n) and each job uses O(log n) binary search, resulting in O(n log n) overall time complexity.

How does GhostInterview help with edge cases?

It guides users to check DP updates for overlapping jobs and ensures correct maximum profit calculations on examples.

Are there common mistakes to avoid in this problem?

Yes, forgetting inclusive end-start scheduling, not using binary search, or miscalculating DP states are frequent errors.

terminal

Solution

Solution 1: Memoization Search + Binary Search

First, we sort the jobs by start time in ascending order, then design a function $dfs(i)$ to represent the maximum profit that can be obtained starting from the $i$-th job. The answer is $dfs(0)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def jobScheduling(
        self, startTime: List[int], endTime: List[int], profit: List[int]
    ) -> int:
        @cache
        def dfs(i):
            if i >= n:
                return 0
            _, e, p = jobs[i]
            j = bisect_left(jobs, e, lo=i + 1, key=lambda x: x[0])
            return max(dfs(i + 1), p + dfs(j))

        jobs = sorted(zip(startTime, endTime, profit))
        n = len(profit)
        return dfs(0)

Solution 2: Dynamic Programming + Binary Search

We can also change the memoization search in Solution 1 to dynamic programming.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def jobScheduling(
        self, startTime: List[int], endTime: List[int], profit: List[int]
    ) -> int:
        @cache
        def dfs(i):
            if i >= n:
                return 0
            _, e, p = jobs[i]
            j = bisect_left(jobs, e, lo=i + 1, key=lambda x: x[0])
            return max(dfs(i + 1), p + dfs(j))

        jobs = sorted(zip(startTime, endTime, profit))
        n = len(profit)
        return dfs(0)

Continue Practicing

#1187 make array strictly increasing #792 number of matching subsequences #2008 maximum earnings from taxi