A repair shop has one mechanic. Job i is jobs[i] = (hours, rate): it takes hours hours
of work, and until it is finished the shop pays that customer's courtesy car at rate
per hour. All customers arrive at time 0, the mechanic works on one job at a time without
breaks or interruptions, so job i finishing at time C costs rate * C.
Return a tuple (total, order): the minimum possible total fee, and the order of job
indices that achieves it. If several orders achieve the minimum, return the
lexicographically smallest list of indices. Empty input gives (0, []).
Examples
Input: jobs = [(3, 1), (1, 2), (2, 2)]
Output: (14, [1, 2, 0])
Explanation: jobs finish at 1, 3 and 6: 2*1 + 2*3 + 1*6 = 14.
Input: jobs = [(2, 0), (1, 1), (2, 2)]
Output: (7, [1, 2, 0])
Explanation: [2, 1, 0] also costs 2*2 + 1*3 = 7, but [1, 2, 0] is smaller.
Constraints
0 <= len(jobs) <= 5 * 10**41 <= hours <= 10**4,0 <= rate <= 10**4- An O(n log n) solution is expected.
Goals
- Derive the order from what happens when two neighbouring jobs swap
- Compare ratios exactly by cross-multiplying, including a zero rate
- Produce the unique answer required by the index tie-break