LeetCode #1235 Hard

Maximum Profit in Job Scheduling

Jobs have start, end, profit. Pick non-overlapping jobs maximizing total profit (touching endpoints allowed).

dpbinary-searchsortingintervals

02

Intuition

💡

Sort jobs by end time and ask, per job: take it or skip it? Skipping inherits the best so far. Taking it earns its profit plus the best achievable among jobs that finish by its start — and because ends are sorted, that predecessor is found by binary search. Weighted intervals break plain greedy; this DP + bisect handles the weights.

03

Approach

1

Sort by end time

dp is built in end-time order: dp[i] = best profit using the first i jobs. dp[0] = 0.

2

Take or skip

dp[i+1] = max(dp[i] / skip /, profit_i + dp[k] / take /), where k = number of jobs ending ≤ start_i — found with bisect_right on the sorted end array.

3

Why greedy fails here

Unweighted interval scheduling is greedy-solvable, but one fat job can beat many thin ones (or vice versa) — profits force trying both branches, which the DP does in O(log n) per job.

04

Solution & live demo

python

▶1from bisect import bisect_right
▶2 
▶3class Solution:
▶4    def jobScheduling(self, startTime, endTime, profit):
▶5        jobs = sorted(zip(endTime, startTime, profit))
▶6        ends = [e for e, _, _ in jobs]
▶7        dp = [0] * (len(jobs) + 1)
▶8        for i, (e, s, p) in enumerate(jobs):
▶9            k = bisect_right(ends, s, 0, i)     # last job ending <= s
▶10            dp[i + 1] = max(dp[i], dp[k] + p)
▶11        return dp[-1]

05

Edge cases

Job ends exactly when another starts

end ≤ start counts as compatible — bisect_right includes it.

All jobs overlap

dp keeps the single most profitable one.

One job

dp = [0, profit].

06

Complexity

Time

O(n log n)

Space

O(n)

Sort + one binary search per job.