Maximum Profit in Job Scheduling: LeetCode 1235 Solution

Maximum Profit in Job Scheduling (#1235) is one of the hardest and most frequently asked interval problems on LeetCode. It sits at the intersection of three fundamental techniques — sorting, binary search, and dynamic programming — and that combination is exactly why interviewers love it.

Companies like Amazon, Google, and DoorDash use this problem in Hard-level assessments because it tests whether you can decompose a complex optimization into clean, composable steps. Brute force is exponential here. The optimal solution is O(n log n), and it requires you to understand why each piece fits together.

In this walkthrough you will learn the problem statement, the sort-by-end-time strategy, the DP recurrence with binary search, a clean implementation, edge cases, and the broader lessons this problem teaches about interval DP.

You are given n jobs. Each job i has a startTime[i], an endTime[i], and a profit[i]. You can choose any subset of non-overlapping jobs to maximize your total profit. Two jobs overlap if one starts before the other ends.

For example, given startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70], the answer is 120. You take job 0 (profit 50, ends at 3) and job 3 (profit 70, starts at 3) — they do not overlap because one ends exactly when the other starts.

The key constraint is that n can be up to 50,000. A brute force approach that tries every possible subset would be O(2^n) — completely infeasible. You need a polynomial-time algorithm, and the right one runs in O(n log n).

The first step is to sort all jobs by their end time. This might seem arbitrary, but it is the key that makes the DP work. When jobs are sorted by end time, you can build up solutions left to right — each new job either extends the best solution so far or gets skipped.

After sorting, define dp[i] as the maximum profit you can earn considering only the first i jobs (in sorted-by-end-time order). The answer will be dp[n], the maximum profit considering all jobs.

Why end time and not start time? Because when you decide whether to include job i, you need to find the last job that finishes before job i starts. With end-time sorting, all candidate non-overlapping jobs are a contiguous prefix of the sorted array — and you can binary search for the boundary.

Sorting takes O(n log n). Everything after this step processes jobs in sorted order, making the DP transitions efficient.

With jobs sorted by end time, the DP recurrence is elegant. For each job i, you have two choices: skip it or take it. If you skip job i, the best profit is dp[i-1]. If you take job i, you earn profit[i] plus the best profit from all jobs that end before job i starts.

The recurrence is: dp[i] = max(dp[i-1], profit[i] + dp[last_non_overlapping]). Here, last_non_overlapping is the index of the last job whose end time is less than or equal to the start time of job i. This is where binary search comes in.

To find last_non_overlapping, you binary search the sorted end times for the largest end time that is less than or equal to startTime[i]. In Python, bisect_right on end times gives you the insertion point — the index just past the last valid job. In other languages, upper_bound serves the same purpose.

Each DP transition takes O(log n) for the binary search, and you do n transitions. Total time: O(n log n) for sorting plus O(n log n) for the DP pass — O(n log n) overall. Space is O(n) for the dp array.

The implementation is straightforward once you understand the recurrence. First, zip the three arrays into tuples and sort by end time. Then build an array of end times for binary searching. Finally, iterate through jobs and fill the dp array.

In Python the core logic fits in about 10 lines. Sort jobs by end time. Initialize dp[0] = 0 (no jobs, no profit). For each job i, use bisect_right to find the last non-overlapping index. Set dp[i+1] = max(dp[i], profit[i] + dp[bisect_result]).

In Java or C++, you use Arrays.sort with a custom comparator and upper_bound (or Collections.binarySearch). The logic is identical — the language-specific part is just how you perform the binary search.

A common implementation mistake is using bisect_left instead of bisect_right. You want the rightmost position where a job ends at or before the current start time. bisect_right on the start time gives the count of jobs that end in time — which is exactly the dp index you need.

Single job: when there is only one job, the answer is simply its profit. The DP handles this naturally — dp[1] = max(dp[0], profit[0] + dp[0]) = profit[0].

All overlapping: if every job overlaps with every other job, you can only pick one. The DP correctly reduces to picking the single most profitable job because no binary search ever finds a valid predecessor.

No overlapping: if no jobs overlap at all, you take every job. The DP accumulates all profits because every binary search finds the immediately preceding job as valid.

Identical times: jobs with the same start and end time overlap with each other but not with jobs ending at their start time. The bisect_right correctly handles the boundary — a job ending at time t does not overlap with a job starting at time t.

This problem is the gold standard for interval DP combined with binary search. It teaches you that complex optimization problems can often be broken into sort + recurrence + efficient lookup. Once you see that pattern, many Hard problems become approachable.

The weighted job scheduling framework generalizes broadly. Any problem where you select non-overlapping intervals to maximize some value — whether it is profit, weight, or count — uses this exact structure. Problems like Maximum Number of Events That Can Be Attended II (#1751) and Maximum Earnings From Taxi (#2008) are direct extensions.

If you are preparing for coding interviews, this is one of the most important Hard problems to master. It tests sorting, binary search, and DP in a single question — three skills that each appear in dozens of other problems. Drill it with YeetCode flashcards until the recurrence and the binary search step feel automatic.

The next time you see "non-overlapping intervals" combined with "maximize profit," you know exactly what to reach for: sort by end time, DP with binary search, O(n log n). That is the pattern.