Problema
All machines start at time 0 and work independently. A machine with time t finishes one item after t seconds, another after 2t seconds, and so on. Find the earliest whole second when their combined production reaches the target.
Implement factory_machines(times, target).
Input
times: Seconds needed for one item on each machine.
target: The number of completed items required.
Output
Return the minimum elapsed seconds.
Restricciones
1 ≤ machines ≤ 200,000. Each time and the target are between 1 and 1,000,000,000. The answer fits signed 64-bit.
Ejemplos
Entrada:
times = [2, 3]
target = 5
Salida esperada:
expected = 6Entrada:
std::vector<long long> times = {2, 3};
long long target = 5;
Salida esperada:
long long expected = 6;Entrada:
long[] times = new long[] {2, 3};
long target = 5;
Salida esperada:
long expected = 6;Explicación
At time 6 the machines have made 3 + 2 = 5 items. At time 5 they have made only 2 + 1 = 3.
Entrada:
times = [4]
target = 3
Salida esperada:
expected = 12Entrada:
std::vector<long long> times = {4};
long long target = 3;
Salida esperada:
long long expected = 12;Entrada:
long[] times = new long[] {4};
long target = 3;
Salida esperada:
long expected = 12;Explicación
One machine completes its third item at 3 × 4 = 12 seconds.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
For any chosen time, you can count how many items all machines together would finish by then.
Pista 2
The answer is the earliest time where that produced count reaches the target.
Pista 3
A monotonic condition like this is well suited to searching over time instead of simulating production.
Complejidad esperada
O(n log T) time, O(1) extra space
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.