Maximum Profit in Job Scheduling — Solution

Problem

You have a list of jobs, each with a start time, an end time, and a profit value. You can run at most one job at a time, but a new job may start the instant another finishes. Find the maximum total profit you can earn by choosing a non-overlapping subset of jobs.

• Input: startTime = [1, 2, 3, 3], endTime = [3, 4, 5, 6], profit = [50, 10, 40, 70]
• Output: 120
• Explanation: Job 0 (time 1→3, $50) then job 3 (time 3→6, $70) yields $120 — taking job 2 instead of job 3 only gives $90.

Intuition

Sort jobs by end time so you can process them in chronological order of completion. For each job the only decision is take it or skip it. If you take it, you want the best profit from all jobs that finish before this one starts — and because the list is sorted, that "last compatible job" boundary can be found with binary search rather than a full scan.

Approach 1 — DP with Linear Scan

Sort jobs by end time. Build a DP table where dp[i] is the maximum profit achievable from any subset of the first i jobs. For each job, either skip it (carry forward dp[i-1]) or take it and pair it with the best compatible prefix found by scanning backwards.

1. Create (endTime, startTime, profit) triples and sort by end time.
2. Set dp[0] = 0; dp[i] will hold the best profit using the first i sorted jobs.
3. For job i, scan backwards through jobs 1…i-1 to find the last one whose end time ≤ this job's start time.
4. Set dp[i] = max(dp[i-1], profit_i + dp[last_compatible]).
5. Return dp[n].

1from typing import List
2
3def jobScheduling(startTime: List[int], endTime: List[int], profit: List[int]) -> int:
4    jobs = sorted(zip(endTime, startTime, profit))  # sort by end time
5    n = len(jobs)
6    dp = [0] * (n + 1)  # dp[i] = max profit from first i jobs
7
8    for i in range(1, n + 1):
9        end_i, start_i, profit_i = jobs[i - 1]
10
11        # Scan backwards for the last job that finishes by start_i
12        last_compatible = 0
13        for j in range(i - 1, 0, -1):
14            if jobs[j - 1][0] <= start_i:  # end time of job j ≤ start of current
15                last_compatible = j
16                break
17
18        dp[i] = max(dp[i - 1], profit_i + dp[last_compatible])
19
20    return dp[n]

Time: O(n²) — sorting is O(n log n), but the inner backwards scan dominates. Space: O(n) — the DP array and the sorted jobs list.

Approach 2 — DP with Binary Search

Identical logic to Approach 1, but replace the backwards linear scan with a binary search on the sorted end-time array. Since jobs are already ordered by end time, "the last job finishing by start_i" is an upper-bound query that resolves in O(log n).

1. Sort jobs by end time and extract their end times into a separate array.
2. For each job i, call bisect_right(end_times, start_i, 0, i) — the return value is the count of previous jobs whose end ≤ start_i, which doubles as the dp index for that compatible prefix.
3. Set dp[i] = max(dp[i-1], profit_i + dp[count]).
4. Return dp[n].

1from bisect import bisect_right
2from typing import List
3
4def jobScheduling(startTime: List[int], endTime: List[int], profit: List[int]) -> int:
5    jobs = sorted(zip(endTime, startTime, profit))  # sort by end time
6    n = len(jobs)
7    end_times = [job[0] for job in jobs]  # extracted for binary search
8    dp = [0] * (n + 1)  # dp[i] = max profit from first i jobs
9
10    for i in range(1, n + 1):
11        end_i, start_i, profit_i = jobs[i - 1]
12
13        # bisect_right returns count of end_times[0:i] that are ≤ start_i,
14        # which is exactly the dp index of the best compatible prefix
15        last_compatible = bisect_right(end_times, start_i, 0, i)
16
17        dp[i] = max(dp[i - 1], profit_i + dp[last_compatible])
18
19    return dp[n]

Time: O(n log n) — sorting plus O(log n) binary search per job. Space: O(n) — the DP array, sorted jobs list, and end-times array.

Complexity Summary

Common Mistakes

• Sorting by start time instead of end time — the DP correctness depends on processing jobs in the order they finish; sorting by start time means earlier dp values can't represent "all non-overlapping predecessors."
• Using bisect_left instead of bisect_right — bisect_left would exclude jobs ending exactly at start_i, but the problem explicitly allows a new job to begin the instant the previous one ends.
• Treating the binary search result as a 0-indexed job position — bisect_right returns a count (how many jobs end by start_i), not a job index; using it directly as dp[last_compatible] is correct because dp is 1-indexed.
• Returning dp[n-1] instead of dp[n] — dp[n] represents the optimal choice over all n jobs; dp[n-1] omits the last job from consideration.
• Forgetting to restrict the binary search range to [0, i) — searching the full end_times array would include jobs not yet processed, though in practice valid inputs (where end > start) make this a no-op, relying on it is fragile.

Related Problems

• non-overlapping-intervals — greedy take on the same "pick non-overlapping intervals" problem, minimizing removals instead of maximizing profit
• merge-intervals — foundational interval overlap detection; understanding this makes the compatibility check here intuitive
• longest-increasing-subsequence — uses the same O(n log n) pattern of DP transitions accelerated by binary search on a sorted auxiliary array
• partition-labels — greedy interval partitioning where "when does an interval close" drives each decision, same structural reasoning
• best-time-to-buy-and-sell-stock-with-cooldown — DP where a "cooldown" constraint links consecutive decisions, the same take-or-skip structure with a compatibility condition