137. Job Sequencing Problem

Given n jobs, each with a deadline and a profit, and each job takes exactly one unit of time to complete (only one job can run per time unit, and a job must finish by its deadline to earn its profit), find the maximum total profit achievable. Jobs are given as n (deadline, profit) pairs.

Input: The first line contains an integer n, the number of jobs. Each of the next n lines contains two space-separated integers, a job's deadline and profit. Output: Print a single integer - the maximum total profit achievable.

1 <= n <= 10^5, 1 <= deadline <= n

Scheduling in the LATEST available slot (not the earliest) is the crucial, slightly counterintuitive detail - it's specifically designed to preserve earlier slots for other jobs that might have earlier deadlines and thus fewer scheduling options.

Schedule jobs (each taking one time unit, each with a deadline and profit) to maximize total profit earned. Brute force: Try every possible subset and ordering of jobs directly, checking deadline feasibility for each - this is exponential, impractical for large n. Optimised: Processing jobs in DESCENDING profit order and always claiming the LATEST available slot before each job's deadline guarantees the highest-value jobs get scheduled whenever physically possible, while preserving as much flexibility (earlier slots) as possible for jobs considered later - this greedy strategy is provably optimal.

Try every possible subset (or every possible assignment of jobs to time slots) and, for each subset that can be scheduled without violating any job's deadline, compute the total profit, keeping track of the best one found. This is correct because it exhaustively considers every feasible schedule, but the number of subsets is exponential in n, making this approach only viable for very small n. Time: O(2^n * n) Space: O(n)

Sort jobs by decreasing profit as before, but instead of scanning slots linearly, use a Disjoint Set Union structure where find(d) returns the latest free slot at or before deadline d. When a job is scheduled at slot s, union that slot with slot s-1 so the next lookup for that region jumps directly to the next available slot. This preserves the same greedy correctness argument as the better approach but replaces the linear slot search with a near-constant-time find operation, making the slot-assignment phase almost linear instead of quadratic. Time: O(n log n) Space: O(n)

Sort jobs in decreasing order of profit. Maintain an array of time slots from 1 to the maximum deadline, initially all free. For each job (highest profit first), scan backward from its deadline down to slot 1 looking for the latest free slot; if one is found, place the job there (locking in its profit), otherwise skip the job. This greedy choice is correct because always taking the highest-profit job first and scheduling it as late as possible preserves the most flexibility for other jobs, but the linear backward scan for a free slot for every job can be slow when deadlines are large. Time: O(n^2) Space: O(n)

1. Sort jobs by PROFIT in descending order. 2. For each job (highest profit first), greedily try to schedule it in the LATEST available free time slot at or before its deadline. 3. Scheduling in the latest available slot (rather than the earliest) is what leaves earlier slots open for other jobs with tighter deadlines.

Time: O(n log n) for sorting, plus O(n * maxDeadline) or O(n log n) with a union-find-based slot allocator for the scheduling pass. Space: O(maxDeadline), for tracking which time slots are occupied.

multiple jobs sharing the same deadline competing for the same slots, a job with deadline 1, and n at its maximum of 10^5 to confirm the sort-and-greedy-slot approach runs efficiently.

Be ready to mention the Union-Find (Disjoint Set) optimization for finding 'the latest free slot at or before X' in near-O(1) amortized time, instead of a naive linear scan backward from the deadline each time - a strong efficiency improvement for large deadline ranges.