327. Weighted Job Scheduling

Given n jobs, each with a start time, a finish time, and a profit, find the maximum total profit obtainable by scheduling a subset of non-overlapping jobs (a job can start only at or after the finish time of the previous job in the chosen subset).

Input: The first line contains n. Each of the next n lines contains a job's start time, finish time, and profit. Output: Print a single integer - the maximum total profit from non-overlapping jobs.

1 <= n <= 10^4

Sorting by FINISH time (not start time) is essential - this ordering guarantees that when processing job i, every job that COULD be a valid predecessor has ALREADY been processed and has its dp value finalized.

Schedule non-overlapping jobs (each with a profit) to maximize total profit. Brute force: Try every possible subset of non-overlapping jobs directly - this is exponential (2^n subsets), impractical for n up to 10^4. Optimised: Sorting by finish time lets each job's decision (skip or take) depend only on the BEST profit achievable using jobs that finish before ITS OWN start time - finding that specific predecessor job via BINARY SEARCH (rather than a linear backward scan) keeps the whole algorithm at O(n log n) instead of O(n²).

Keep the same sorted-by-finish-time dp[i] = max(dp[i-1], profit[i] + dp[j]) recurrence as the better approach, but since jobs are sorted by finish time, the finish times form an ascending array that can be binary searched: find the latest job whose finish time is at most job i's start time using binary search instead of a linear backward scan. Replacing the linear predecessor search with a binary search cuts the per-job cost from O(n) down to O(log n), so the overall time is dominated by the initial sort. Time: O(n log n) Space: O(n)

Recursively consider each job in some fixed order and branch on whether to include it (skipping ahead to the next job that starts at or after its finish time) or exclude it (moving to the next job regardless), taking the maximum profit over both branches, with a base case of zero profit once no jobs remain. This directly explores every possible subset of non-overlapping jobs, so it is guaranteed correct, but the number of branches doubles at every job, giving exponential blowup. Time: O(2^n) Space: O(n)

Sort jobs by finish time, and define dp[i] as the best achievable profit using only the first i jobs in this sorted order: dp[i] = max(dp[i-1], profit[i] + dp[j]) where j is the largest index whose finish time is at most job i's start time, found by scanning backward through all earlier jobs. Sorting first turns the exponential subset search into a well-defined linear chain of decisions, but finding each job's latest compatible predecessor by scanning is itself linear, so building the whole dp array costs quadratic time overall. Time: O(n^2) Space: O(n)

1. Sort all jobs by FINISH time. 2. dp[i] = best profit achievable using only the first i jobs (in sorted order); for job i, either SKIP it (dp[i-1]) or TAKE it: its profit plus dp[l], where l is the largest index BEFORE i whose finish time is at most job i's start time. 3. Finding l via BINARY SEARCH (since jobs are sorted by finish time) is the standard way to make this scale, though a backward scan also works within smaller constraints.

Time: O(n log n) with binary search for finding each job's compatible predecessor; O(n²) with a naive backward linear scan. Space: O(n), for the dp array and the sorted job list.

Test n = 1 (answer is that single job's profit), a set of jobs that all mutually overlap (answer is just the single most profitable job), and n = 10^4 (upper bound), which favors sorting plus binary search over a full backward scan.

Be ready to mention binary search explicitly as the standard way to scale this to larger n - a full backward scan works correctly but degrades to O(n²), which interviewers often specifically ask you to improve upon as a follow-up.