Todos los desafíos
Intermedio 1 resuelto 100.0% de aceptación

Factory Production Time

Find the earliest time parallel machines can finish a target number of items.

Lo que aprenderás

  • Binary search over time instead of items
  • Check if a time is enough in one pass
  • Pick safe search bounds

Problema

Ver traducción

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

Ejemplo 1
Entrada:
times = [2, 3]
target = 5

Salida esperada:
expected = 6
Entrada:
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.

Ejemplo 2
Entrada:
times = [4]
target = 3

Salida esperada:
expected = 12
Entrada:
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.

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

# Programador Lenguaje Tiempo Memoria Revisión de IA Solución
1 ННикита Python 847 ms - 5/5 Ver código

Aprende de otros

Soluciones de la comunidad

Alerta de spoiler: 1 solución completa abajo Intenta resolverlo tú mismo primero. Igual puedes ver el código de otros desarrolladores y las reseñas de IA. Inicia sesión y resuelve el reto para unirte a la discusión.