A sign painter has been offered commissions jobs, where jobs[i] = [hours, due]: the sign takes
hours hours of work and must be finished no later than hour due. She starts at hour 0,
works on one sign at a time without breaks, and may turn down any commissions she likes. A sign
that is started must be finished before the next one is started.
Return [most, hours]: most is the largest number of commissions she can finish on time, and
hours is the smallest total number of working hours among all ways of finishing most
commissions on time. With no jobs (or none that can be finished) return [0, 0].
Examples
Input: jobs = [[3, 4], [2, 5], [4, 9], [5, 9]]
Output: [3, 9]
Explanation: paint the 3-hour, 2-hour and 4-hour signs in that order: they finish
at hours 3, 5 and 9. All four cannot be finished on time.
Input: jobs = [[4, 4], [1, 5], [1, 5]]
Output: [2, 2]
Explanation: two signs is the best. [4, 4] with one [1, 5] also works but takes
5 hours; the two 1-hour signs take only 2.
Constraints
0 <= len(jobs) <= 2 * 10**51 <= hours <= 10**4,1 <= due <= 10**9- A quadratic method is too slow for the largest tests.
Goals
- Process jobs in order of due time and keep the accepted set feasible
- Repair an overflow by dropping the longest accepted job, and prove why that is safe
- Get the least total working time among all best schedules as a by-product