The shortest remaining
n submissions arrive at a judging server. Submission i arrives at time ri and needs pi milliseconds of core time. There is one core, and at each moment it works on one submission, but it can interrupt it at any moment, turn to another and come back later: work done is not lost, and switching costs nothing. A submission cannot be started before it arrives. A submission’s turnaround time runs from its arrival to the moment its work is done.
Find the smallest possible sum of the turnaround times of all submissions. The tests include all the tests of the catalogue’s problems with the real times of the reference solutions, arriving at random moments.
Input
The first line holds the number of submissions n (1 ≤ n ≤ 105). Then n lines “ri pi” in any order: 0 ≤ ri ≤ 1011, 1 ≤ pi ≤ 106. Several submissions may arrive at the same moment.
Output
One number: the smallest sum of turnaround times.
In the first example the five-millisecond submission starts at once, but short ones arrive at times 1 and 2: if the core preempts for them, each has a turnaround of 1 ms, and the long one finishes at time 7, 9 in all. Without preemption it would be 5 + 5 + 5 = 15. In the second example the core is idle from time 6 to 10, and the submission arriving at time 4 arrives exactly when the first finishes.
Examples
Example 1
3 0 5 1 1 2 1
9
Example 2
5 10 3 0 4 4 2 10 1 13 2
14
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
If all submissions arrived at once, the best order would be “shortest first”. What changes when they arrive one at a time? What is known about the submission the core is running now, at the moment a new one arrives?
2The idea
Always work on the submission with the least left, and preempt it if a submission with an even smaller remainder arrives. This is the SRPT rule, and the article proves that its sum of turnaround times is smallest: if at some moment the core works on submission j although submission i has a smaller remainder, swap their future work, finishing i first in the same time slots. Submission i finishes no later than the first of the two finished before, and j at the time the second did, so the sum does not grow.
Decisions about what to run are needed only at moments of arrival and completion: between them the submission with the smallest remainder stays smallest, since its remainder only decreases.
3Walkthrough
Sort the submissions by arrival time. Keep a heap of pairs “remainder, number” and the current time t. If the heap is empty, jump to the next arrival. Push everything that has arrived by t and take the submission with the smallest remainder. If it can finish before the next arrival, finish it and add its turnaround time to the answer. Otherwise work on it until the next arrival, reduce its remainder and push it back.
Each arrival interrupts the work at most once, so there are O(n) events. The sum reaches 1016: in Go a 64-bit int is needed.
3+Solution
4Complexity
O(n log n): a sort and O(n) heap operations.
5Common mistakes
- No preemption. “Shortest next” is good while everything arrives at once, but when submissions arrive one at a time, a long one started slightly earlier holds everyone up. The first example: 15 instead of 9.
- Comparing the full length instead of the remainder. An almost finished long submission is shorter by remainder than a new medium one, and preempting it for the new one is a loss.
- Stepping millisecond by millisecond. The answer is the same, but moments reach 1011: step from event to event.
Algorithms behind it
O(n log n): a sort or a heap
2 problems
DS
Data structure
Binary heap
The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on.
O(log n)
2 problems