Minimum Time with 2 Scanners
Problem Overview
Both scanners can run at the same time, and each one finishes its own pile of documents on its own clock.
Intuition
Both scanners can run at the same time, and each one finishes its own pile of documents on its own clock. If the faster scanner takes i documents and the slower one takes the rest, the job ends at the later of i times s1 and (n minus i) times s2. As i grows, the first side rises and the second side falls, so the maximum of the two sides first drops and then rises. The lowest point sits where the two sides meet, which is near n times s2 over s1 plus s2. Only the floor and the next integer of that balance need to be checked. Putting every document on the faster scanner is also compared, because that choice can win when the slower scanner is much slower. Products are kept in 64 bit integers so a large n times a large scan time does not wrap.
Algorithm
- 1Swap the two scan times when needed so that s1 is the faster scanner.
- 2Start the answer at n times s1, the time to give every document to the faster scanner.
- 3Compute i as the floor of n times s2 divided by s1 plus s2.
- 4For i and for i plus 1, when the index lies between 0 and n, take the maximum of that scanner load and the other scanner load.
- 5Keep the smallest of those finish times and return it.
Example Walkthrough
Input: n = 2, s1 = 1, s2 = 3
- 1. Scanner 1 is faster. Giving both documents to it finishes in time 2.
- 2. The balance point is near 2 times 3 over 4, which is 1.5, so the candidates are 1 and 2 documents on scanner 1.
- 3. One document each finishes at max(1, 3) = 3, which is worse than 2, so the answer is 2.
Output: 2
Common Pitfalls
- • The finish time is the maximum of the two scanners, not their sum. They work at the same time.
- • A distribution that leaves the slower scanner idle can still be best when that scanner is much slower than the other.
- • Use 64 bit products for i times s1 and for (n minus i) times s2. Both factors can be large enough to overflow a 32 bit integer.
- • Only the floor of the balance and the next integer are required. A full sweep over every i is unnecessary.
// Approach: Give i documents to the faster scanner and the rest to the
// slower one. The finish time is max(i * s1, (n - i) * s2), which falls
// then rises as i grows. The minimum sits where the two sides meet, so
// only the floor and ceil of n * s2 / (s1 + s2) need to be checked, along
// with putting every document on the faster scanner.
// Complexity: O(1) time, O(1) extra space.
class Solution {
public int minTime(int n, int s1, int s2) {
if (s1 > s2) {
int tmp = s1;
s1 = s2;
s2 = tmp;
}
long best = (long) n * s1;
int i = (int) (((long) n * s2) / ((long) s1 + s2));
for (int k = i; k <= i + 1; k++) {
if (k < 0 || k > n) {
continue;
}
long cur = Math.max((long) k * s1, (long) (n - k) * s2);
if (cur < best) {
best = cur;
}
}
return (int) best;
}
}