A copy shop has one printer and one binding machine. orders[i] = [p, b] means order i needs
p minutes on the printer and then b minutes on the binder. You choose one sequence of the
orders; both machines work through the orders in that sequence, one at a time, starting at
minute 0. The printer runs the orders back to back. The binder starts an order as soon as both
it has finished the previous order and the printer has finished this one:
print_done[k] = print_done[k - 1] + p_k
bind_done[k] = max(bind_done[k - 1], print_done[k]) + b_k
(with both values 0 before the first order). Return the smallest possible bind_done of the
last order over all sequences. An empty list returns 0.
Examples
Input: orders = [[3, 2], [1, 4], [4, 3]]
Output: 10
Explanation: The given sequence finishes at 12. The sequence [1, 4], [4, 3], [3, 2]
prints until 1, 5, 8 and binds until 5, 8, 10.
Input: orders = [[5, 1]]
Output: 6
Constraints
0 <= len(orders) <= 10**5,1 <= p, b <= 10**4- Target complexity: O(n log n). Trying all sequences is hopeless beyond about ten orders.
Goals
- Simulate a two-stage pipeline where the second stage waits for the first
- Derive an ordering rule by comparing two neighbouring jobs
- Turn a pairwise rule into a single sort with two groups