Generated by Codex with GPT 5.6 Sol High

Quick facts

The problem in plain language

Each job has a start time, an end time, and a profit. The goal is to choose a set of jobs that do not overlap and earn as much total profit as possible. A job ending at time x is compatible with one starting at time x.

This is weighted interval scheduling. Ordinary interval scheduling can greedily maximize the number of jobs by always taking the next job that ends earliest. That greedy rule fails here because one long, valuable job may be worth more than several short jobs. The choice has to account for both compatibility and profit.

Deriving the optimal solution

Sort the jobs by end time. After that, imagine solving progressively larger prefixes of the sorted list.

For every job, there are only two meaningful choices:

  1. Skip it. The answer stays equal to the best profit from all earlier jobs.
  2. Take it. Add its profit to the best answer that finishes no later than this job starts.

Let best_profit[i] be the maximum profit available from the first i jobs. For the ith job, binary search the sorted end times to find how many earlier jobs end at or before its start time. Call that number compatible_count. The transition is:

best_profit[i] = max(
    best_profit[i - 1],
    best_profit[compatible_count] + current_profit,
)

The key insight is that taking the current job rules out only the overlapping jobs. Everything ending before it starts has already been summarized by one dynamic-programming entry, so there is no need to reconsider those schedules individually.

Why the recurrence is complete

Consider an optimal schedule drawn from the first i jobs. It either excludes the ith job, in which case its value cannot exceed best_profit[i - 1], or includes it. If it includes the job, every other chosen job must end by the current start time, and the best possible profit from those compatible jobs is exactly best_profit[compatible_count]. The recurrence evaluates both exhaustive cases and keeps the better one.

Sorting costs O(n log n). Each of the n jobs performs one binary search, so the dynamic program also costs O(n log n) overall. The arrays use O(n) extra space.

Python solution

from bisect import bisect_right


class Solution:
    def jobScheduling(
        self,
        startTime: list[int],
        endTime: list[int],
        profit: list[int],
    ) -> int:
        """Return the maximum profit from a non-overlapping set of jobs."""
        if not (len(startTime) == len(endTime) == len(profit)):
            raise ValueError("startTime, endTime, and profit must have equal lengths")

        # End-time order makes every compatible predecessor part of a prefix.
        jobs = sorted(zip(endTime, startTime, profit))
        sorted_end_times = [end for end, _, _ in jobs]

        # best_profit[i] is the optimum using only the first i sorted jobs.
        best_profit = [0] * (len(jobs) + 1)

        for job_count, (_, start, reward) in enumerate(jobs, start=1):
            # Search only earlier jobs. bisect_right includes jobs whose end
            # time equals this start time, because touching jobs may coexist.
            compatible_count = bisect_right(
                sorted_end_times,
                start,
                hi=job_count - 1,
            )

            profit_if_skipped = best_profit[job_count - 1]
            profit_if_taken = best_profit[compatible_count] + reward
            best_profit[job_count] = max(profit_if_skipped, profit_if_taken)

        return best_profit[-1]

Interview follow-ups

How would you return the chosen jobs, not just the profit?

Store the predecessor index found by binary search for every job. While filling the DP table, also record whether taking the current job strictly beats skipping it. Then walk backward: if a job was skipped, move to the previous DP state; if it was taken, add it to the answer and jump to its predecessor state. Reverse the collected jobs at the end. The asymptotic bounds remain O(n log n) time and O(n) space.

When profits tie, the interviewer may ask for a deterministic policy such as choosing fewer jobs or the lexicographically earliest sequence. That secondary goal must be represented in the DP state or handled by an explicit tie-breaking rule.

What changes if at most k jobs may be selected?

Add a second DP dimension. Let best[i][j] be the maximum profit from the first i jobs while taking at most j of them. Skipping uses best[i - 1][j]; taking uses the compatible predecessor state plus the current reward: best[p][j - 1] + reward.

Precomputing every predecessor with binary search takes O(n log n). The DP then takes O(nk) time and O(nk) space, or O(n) space per layer if job reconstruction is unnecessary. The extra dimension is essential because a schedule’s profit alone no longer says how much of the job budget remains.

What if jobs arrive online in end-time order?

Maintain the best achievable profit keyed by end time. For an arriving job, query the largest profit at any time no later than its start, add the job’s profit, and update its end time with that candidate if it improves the stored result. With known timestamps, coordinate compression plus a Fenwick tree or segment tree supports each query and update in O(log n) time.

This works because end-time arrival preserves the same dependency order as the offline DP. If jobs arrive in arbitrary order, a later arrival may improve states that have already been used, so the simple one-pass invariant no longer holds without a more sophisticated dynamic structure or recomputation.

What if choosing no job is forbidden?

The current table starts at zero, which intentionally permits the empty schedule. If at least one job must be selected and profits may be negative, initialize unreachable states to negative infinity and track whether a real job has been chosen. Another clean formulation keeps two states: the best value allowing an empty schedule and the best value requiring a nonempty one.

With the original constraint that every profit is positive, this distinction does not change the answer, but making the state semantics explicit prevents a subtle bug when the constraints change.

What if a job starting exactly when another ends counts as overlapping?

Change the predecessor search from “last end time less than or equal to the start” to “last end time strictly less than the start.” In Python, that means replacing bisect_right(sorted_end_times, start, ...) with bisect_left(sorted_end_times, start, ...).

The DP recurrence stays identical; only the compatibility boundary changes. This is a useful interview check because choosing the wrong binary-search variant can produce an otherwise convincing but incorrect solution.

Could the jobs be sorted by start time instead?

Yes. Define a suffix DP where best[i] is the maximum profit obtainable from job i onward. For each job, binary search for the first later job whose start time is at least the current end time. Then compare skipping to best[i + 1] against taking the current profit plus best[next_index].

That version has the same O(n log n) time and O(n) space bounds. End-time prefix DP and start-time suffix DP are mirror images; choosing between them is mostly a matter of which recurrence feels easier to explain and implement correctly.

Takeaway

When choices occupy intervals and carry different values, first impose an order that turns compatible earlier choices into a prefix or suffix. Dynamic programming summarizes the best value of that region, and binary search finds the correct boundary quickly. That combination—sorting, a two-way take-or-skip recurrence, and binary search—is the reusable pattern behind weighted interval scheduling.