Two-Desk Ballot Batch Pipeline
Minimum completion time for an array of two-stage processing times
An election office processes sealed ballot batches through two desks: a verification desk followed by a counting desk.
For batch i, batches[i] = [verification, counting] gives its processing time at each desk. A batch must finish verification before its counting can begin.
Each desk can process only one batch at a time, and processing a batch cannot be interrupted. The two desks may work simultaneously on different batches. All batches are available at time 0, and moving a batch between desks takes no time.
You may choose any order of the batches, but both desks must process batches in that same order. A desk may wait when its next batch is not yet available.
Return the smallest possible time at which every batch has finished counting. If there are no batches, return 0.
Examples
Example 1
Input: batches = [[4,9],[7,2],[3,5]] Output: 19
One optimal order is batch 2, then batch 0, then batch 1. The counting desk can work on an earlier batch while the verification desk prepares a later one.
Example 2
Input: batches = [[8,1],[2,7],[4,4]] Output: 15
An optimal order places the batch with a short verification time and long counting time first, and the batch with a long verification time and short counting time last.
Example 3
Input: batches = [] Output: 0
There are no batches, so neither desk needs to perform any work.
Constraints
- 0 <= batches.length <= 3000
- Every batches[i] contains exactly two integers.
- 1 <= batches[i][0], batches[i][1] <= 1000000
The intended solution takes O(n log n) time and O(n) auxiliary space. The result can exceed a signed 32-bit integer, but remains exactly representable by a JavaScript Number.
Hints
Show hint 1Hint 1
For two consecutive batches, compare the completion time obtained by putting one before the other versus reversing them.
Show hint 2Hint 2
Separate batches whose verification time is no greater than their counting time from the remaining batches. Consider which group belongs near the beginning and how to sort each group.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return one optimal batch order along with the minimum completion time?
- If the verification order were fixed in advance, how would you compute the earliest completion time in linear time?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem