You’re in a coding interview. The interviewer says: “You have a list of jobs, each with a start time, end time, and profit. Find the schedule that maximizes profit without overlapping jobs.” This is a weighted job scheduling problem: DP combined with binary search. Maximum Profit in Job Scheduling is LeetCode #1235, and it’s the type of Hard problem that rewards candidates who can reduce it to a clean DP recurrence.

This walkthrough covers sorting by end time, the include-or-exclude transition, and the binary search that makes the DP efficient.

---

The Problem

You have n jobs. The ith job starts at startTime[i], ends at endTime[i], and pays profit[i]. Find the maximum profit you can achieve by scheduling non-overlapping jobs. (LeetCode #1235)

Example 1

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

Output 120

Schedule jobs 1 and 4 (times [1,3] and [3,6], profits 50 + 70 = 120).

Example 2

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

Output 150

Schedule jobs 1, 4, 5 (times [1,3], [4,6], [6,9], profits 20 + 70 + 60 = 150).

Already comfortable with the solution? Practice it in a mock interview →

---

What Interviewers Are Actually Testing

This problem tests whether you can formulate a DP recurrence with binary search as a subroutine. It’s the weighted version of the classic interval scheduling problem, and it separates candidates who can design DP from scratch from those who only recognize standard patterns.

Skill	What Interviewers Observe
DP recurrence	Do you define dp[i] as max profit considering first i jobs sorted by end time?
Binary search for compatible job	Do you use bisect_right to find the latest job ending at or before the current start?
Sort by end time	Do you recognize sorting by end time as the key preprocessing step?
Include/exclude transition	Can you articulate “include or skip” the current job?

---

Step 1: Clarifying Questions

1. Can jobs have the same start and end time? A job with startTime == endTime has zero duration. The problem allows it. Two jobs where one ends at the same time another starts are non-overlapping (e.g., [1,3] and [3,5] are compatible).

2. Can all jobs overlap? Yes. In the worst case, you pick the single most profitable job.

3. Are profits always positive? Yes, profit[i] >= 1. This means you’d never skip a job unless it conflicts with a more profitable combination.

---

Step 2: A First (Non-Optimal) Idea

Try all subsets of non-overlapping jobs and take the maximum profit. This is O(2^n), clearly impractical for n up to 50,000.

The key observation: once jobs are sorted by end time, the problem has optimal substructure. For each job, you either include it (adding its profit to the best result from compatible earlier jobs) or skip it (carrying forward the previous best).

Approach	Time	Space
All subsets	O(2^n)	O(n)
DP without binary search	O(n^2)	O(n)
DP + binary search	O(n log n)	O(n)

---

Step 3: The Key Insight

Sort jobs by end time. For each job, the DP choice is: include it or skip it. If you include job i, add its profit to the best result achievable by jobs ending at or before startTime[i]. Find that compatible job with binary search. dp[i] = max(dp[i-1], profit[i] + dp[latest_compatible]).

The binary search is what makes this O(n log n) instead of O(n^2). Without it, finding the latest compatible job for each new job would require a linear scan.

---

Step 4: Optimal Strategy

1. Sort jobs by end time.
2. Maintain a dp array of (end_time, max_profit) tuples, initialized with [(0, 0)] as the base case.
3. For each job (sorted by end time):
   • Binary search dp to find the latest entry with end_time <= start_time of the current job.
   • Compute best_with_job = dp[found_index].profit + current_profit.
   • If best_with_job > dp[-1].profit, append (current_end, best_with_job) to dp.
4. Return dp[-1].profit.

The dp array is monotonically increasing in both end time and profit. Only appending when the profit improves ensures this monotonicity, which is needed for binary search correctness.

---

Python Implementation

from bisect import bisect_right

def jobScheduling(startTime: list[int], endTime: list[int], profit: list[int]) -> int:
    jobs = sorted(zip(endTime, startTime, profit))
    # dp[i] = (end_time, max_profit) — monotonically increasing in both dimensions
    dp = [(0, 0)]  # base case: 0 jobs, 0 profit

    for end, start, p in jobs:
        # Find latest job ending at or before `start`
        idx = bisect_right(dp, (start, float('inf'))) - 1
        best_with_job = dp[idx][1] + p

        if best_with_job > dp[-1][1]:
            dp.append((end, best_with_job))
        # else: skip (dp stays the same — only append if it improves)

    return dp[-1][1]

Why this is interview-friendly:

• bisect_right with (start, float('inf')) finds the right insertion point. Since dp stores (end_time, profit) tuples and float('inf') is larger than any profit, bisect_right returns the index after all entries with end_time <= start. Subtract 1 to get the latest compatible entry.
• Monotonic dp array. Only appending when profit improves keeps dp sorted in both dimensions, which is required for binary search to work.
• No explicit skip tracking. If the current job doesn’t improve the best profit, we simply don’t append. The last element of dp always holds the best achievable profit.

---

Time & Space Complexity

	Time	Space
Maximum Profit in Job Scheduling	O(n log n)	O(n)

Sorting is O(n log n). Each binary search is O(log n). The dp array has at most n entries.

---

Common Interview Mistakes

1. Not sorting by end time. The DP recurrence requires jobs ordered by end time so “all previous jobs” means “all jobs with smaller end times.” Sorting by start time doesn’t give the right subproblem structure.

2. Binary searching on the wrong field. You need the latest job with end_time <= start_time[current]. The dp array stores (end_time, profit) tuples, and you search the end_time dimension.

3. Forgetting the base case (0, 0). Without it, jobs with no compatible predecessors have no dp entry to fall back on. The base case represents “take no jobs, earn 0 profit.”

4. Appending every job to dp unconditionally. Only append if the new profit exceeds the current maximum. dp must be monotonically increasing in profit for bisect_right to return correct results.

---

What a Strong Candidate Sounds Like

“I’ll sort jobs by end time, then use DP. For each new job, I binary search the dp array to find the latest job ending at or before the new job’s start time, that’s the best prior state I can build on. The transition is: take the max of skipping the current job (carry forward the last dp value) or including it (prior dp value + current profit). O(n log n) time.”

---

Example Interview Dialogue

Interviewer: Walk through startTime=[1,2,3,3], endTime=[3,4,5,6], profit=[50,10,40,70].

Candidate: Sort by end time: jobs are (3,1,50), (4,2,10), (5,3,40), (6,3,70). dp = [(0,0)]. Job (3,1,50): search for end <= 1, find (0,0). best = 0+50 = 50 > 0, append (3,50). dp = [(0,0),(3,50)]. Job (4,2,10): search for end <= 2, find (0,0). best = 0+10 = 10 < 50, skip. Job (5,3,40): search for end <= 3, find (3,50). best = 50+40 = 90 > 50, append (5,90). dp = [(0,0),(3,50),(5,90)]. Job (6,3,70): search for end <= 3, find (3,50). best = 50+70 = 120 > 90, append (6,120). Answer: 120.

Interviewer: Why can’t you sort by start time instead?

Candidate: Sorting by start time doesn’t give the DP the right subproblem structure. When processing a job, you need all previous non-conflicting jobs to already have their optimal solutions computed. “Previous” needs to mean “ending before my start,” which requires sorting by end time.

---

Related Problems

• Non-overlapping Intervals (LeetCode #435). Greedy interval scheduling: minimize removals to eliminate overlaps.
• Merge Intervals (LeetCode #56). Interval manipulation fundamentals.
• Coin Change (LeetCode #322). DP with optimal substructure, same include-or-exclude pattern.
• Meeting Rooms (LeetCode #252). Simplest interval scheduling check.

---

Practice This in a Mock Interview

Maximum Profit in Job Scheduling is a Hard problem where the DP recurrence + binary search combination is the key. Understanding why sorting by end time is necessary, and what the bisect_right on dp end times actually finds, is what separates a complete answer from a confused one.

Start a mock interview for Maximum Profit in Job Scheduling on Intervu.

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap and study plans
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub, condensed solutions with code