1482. What the Earliest-Finishing Rule Leaves on the Table

n jobs are offered. Job i occupies the HALF-OPEN stretch [a, b) with a < b and pays w. Two jobs may both be taken when they do not overlap; jobs that merely TOUCH, one ending exactly where the next begins, may both be taken.

Print two integers on one line:

first what this exact greedy collects: sort the jobs by b ascending, then by a ascending, then by the order they were given in the input; walk that order and take a job when its a is at least the b of the last job taken second the largest total pay any valid set achieves

(1,3) pay 50, (2,5) pay 20, (4,6) pay 70, (6,7) pay 60 -> 180 180 (0,5) pay 10, (1,2) pay 4 -> 4 10 (1,2) pay 1, (1,2) pay 5, (3,4) pay 1, (3,4) pay 5 -> 2 10

The second line is the smallest failure. The greedy sorts by end, so (1,2) comes first and is taken for 4; (0,5) then starts at 0, which is below 2, so it is skipped. The greedy collects 4 and the truth is 10.

The third line shows the failure without any nesting at all. Each pair of jobs occupies the same stretch, and the greedy's tie-break settles on input order, so it takes the job paying 1 from each pair: 2 against 10.

## What most people try first

Assuming the greedy is right, because it IS right when every job pays the same. There it maximises the NUMBER of jobs taken, and with equal pay that maximises the total. The moment the pays differ, ending early stops being the only thing that matters: a job ending later may be worth more than everything that fits after it.

## Two answers, two methods

The greedy is a direct simulation. Sort, walk, take when it fits.

last = nothing greedy = 0 for each job in (b, a, input index) order: if last is nothing or a >= last: greedy += w; last = b

The truth is a table, taking or skipping each job in end order:

sort by b ascending; ends[i] = the end of the i-th job in that order dp[0] = 0 for i in 1 .. n: (a, b, w) = job i j = how many of the first i-1 jobs end at or before a binary search dp[i] = max(dp[i-1], w + dp[j]) best = dp[n]

Both are O(n log n).

## Why the table is exact and the greedy is not

For the table: the best set using the first i jobs either omits job i, which is dp[i-1], or takes it, in which case every other member must end at or before a and so lies among the first j, giving w + dp[j]. Both cases are reachable, so the maximum of the two is exact.

For the greedy: the exchange argument that works for equal pay swaps a job for the one ending earliest and claims the swap loses nothing. With pays attached the swap loses w_old - w_new, which can be any amount, so the argument collapses at its first step. No repair is possible, because the counterexample survives every tie-break: the third sample defeats it whichever way the ties are broken, since the pairs are identical in shape.

## Why the greedy needs an exact tie-break to be a well-posed question

A greedy is only a definite answer once the order it walks is definite. Two jobs with the same b and the same a and different pay must be visited in a stated order, or the first number printed depends on the sort's internal behaviour. The order fixed above is b, then a, then input index, which makes the sort stable by construction.

## The boundary that breaks a careless implementation

Both halves need a >= last and ends <= a, non-strict, because touching jobs may both be taken. Making either strict loses the chains of touching jobs, and the fifth test is three touching jobs where both answers are 3.

## Overflow

2 * 10^5 jobs paying 10^9 reach 2 * 10^14, far past the 2147483647 a signed 32 bit integer holds, so both totals need 64 bits. Two such jobs reach 2 * 10^9, which still FITS in a signed 32 bit integer.

## Related

Problem 468 asks only for the optimum, under the same half-open rule, and is the pure form of weighted interval scheduling. Problem 1437 is the unweighted question, where the greedy is correct and provably so. Printing both numbers here is deliberate: it turns "the greedy is wrong" from an assertion into an output you can watch diverge.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a < b ≤ 10^9` - `1 ≤ w ≤ 10^9` - each job occupies the half-open stretch `[a, b)`, so jobs that merely touch may both be taken - the greedy walks the jobs sorted by `b` ascending, then `a` ascending, then input order, and takes a job when its `a` is at least the `b` of the last job taken