Car Fleet

Q: Qual é a complexidade de tempo do Car Fleet?

Ordenar por posição leva O(n log n) e a passagem com uma pilha leva O(n) , então o total é de O(n log n) de tempo e O(n) de memória. Verificar cada carro em relação a todos os carros à frente leva O(n²) .

Q: Como comparar horários de chegada sem usar ponto flutuante?

O tempo de chegada é dist / speed . Como as velocidades são positivas, d1 / s1 > d2 / s2 é válido exatamente quando d1 × s2 > d2 × s1 . Ambos os lados são inteiros de até 10^12 , então calcule-os em um tipo de 64 bits; assim, a comparação é exata, sem necessidade de considerar arredondamentos.

MédioPilha Ordenação

+10

Os carros trafegam por uma estrada de uma faixa em direção ao marco target. O carro i começa no marco position[i] e trafega a speed[i] milhas por hora. Nenhum carro pode ultrapassar outro: um carro que alcança um mais lento permanece logo atrás dele e, a partir daí, os dois se movem juntos, na velocidade mais baixa, como uma única frota.

Um carro sozinho também forma uma frota, e um carro que alcança uma frota exatamente no destino se junta a ela. Retorne o número de frotas que chegam ao destino.

Função

carFleet(target: integer, position: integer-array, speed: integer-array) → integer

targetinteger: o quilômetro para onde todos os carros estão indo
positioninteger-array: o quilômetro inicial de cada carro
speedinteger-array: a velocidade de cada carro, em milhas por hora
Retornainteger: o número de frotas que chegam ao destino

Restrições

n == position.length == speed.length
1 ≤ n ≤ 10⁴
1 ≤ target ≤ 10⁶
0 ≤ position[i] < target
1 ≤ speed[i] ≤ 10⁶
Todas as posições são diferentes.

Exemplos

Entrada: target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
Saída: 2
Explicação: Sozinhos, os carros nas milhas 17, 14, 8 e 2 precisam de 3, 2, 3 e 3 horas, então o carro na milha 14 alcança o da milha 17, e os outros dois os alcançam na milha 20. O carro na milha 0 precisa de 10 horas e chega sozinho.

Entrada: target = 9position = [0, 4, 7]speed = [1, 2, 3]
Saída: 3
Explicação: Os carros nas milhas 7, 4 e 0 precisam de 2/3, 5/2 e 9 horas. Cada um chegaria depois do carro à sua frente, então ninguém alcança ninguém: 3 frotas.

Para ir além

As posições são números inteiros menores que target. Você consegue contar as frotas em tempo O(n + target), sem uma ordenação por comparação?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Em uma faixa, os carros nunca mudam de ordem, e o que determina tudo é quando cada carro chegaria sozinho: (target - position[i]) / speed[i]. Percorra os carros, começando pelo mais próximo do destino e seguindo para trás. Um carro inicia uma nova frota somente quando chegaria estritamente depois da frota à sua frente.

Verifique todos os carros à frente

Correta, mas não termina nos maiores testes

Intuição

Um carro lidera uma frota exatamente quando todos os carros à sua frente chegariam estritamente antes se estivessem sozinhos. Se algum carro à frente chegaria no mesmo instante ou depois, seu carro o alcança, ou alcança sua frota, até o destino. Se todos chegarem antes, nada à frente poderá atrasá-lo, pois uma frota chega no horário mais tardio entre os horários de chegada individuais de seus carros. Conte os carros líderes, comparando os tempos exatamente por meio da multiplicação cruzada.

Cada carro percorre todos os n carros: 10^8 verificações para n = 10^4.

Algoritmo

Defina fleets = 0.
Para cada carro i, examine todos os carros j com position[j] > position[i].
Se algum j satisfizer (target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j], o carro i é alcançado: ignore-o.
Caso contrário, o carro i lidera uma frota: adicione 1 a fleets.
Retorne fleets.

def carFleet(target, position, speed):
    n = len(position)
    fleets = 0
    for i in range(n):
        dist = target - position[i]
        caught = False
        for j in range(n):
            # Car j is ahead and would not arrive before car i: car i catches it.
            # (target - position[j]) / speed[j] >= dist / speed[i], without division.
            if position[j] > position[i] and (target - position[j]) * speed[i] >= dist * speed[j]:
                caught = True
                break
        if not caught:
            fleets += 1
    return fleets

Ordene por posição e empilhe as frotas

Intuição

Ordenados por posição, com o mais próximo do destino primeiro, os carros à frente do atual são exatamente aqueles que já foram vistos, já em frotas. Mantenha as frotas em uma pilha, cada uma armazenada como a distância e a velocidade do seu carro da frente, que determina o tempo de chegada da frota.

Só o topo importa. Cada elemento empilhado chega estritamente depois da frota abaixo dele, então os tempos aumentam da base ao topo, e chegar depois do topo significa chegar depois de todos os carros à frente.

O Exemplo 1, em ordem, contém os carros nas posições 17, 14, 8, 2 e 0, com distância dividida pela velocidade 3/1, 6/3, 12/4, 18/6, 20/2. Empilhe (3, 1). O carro na posição 14 se junta, pois 6 × 1 > 3 × 3 é falso. O carro na posição 8 empata, 12 × 1 = 3 × 4, e se junta, assim como o carro na posição 2. Para o carro na posição 0, 20 × 1 > 3 × 2: empilhe.

Algoritmo

Ordene os índices dos carros por posição, do maior para o menor.
Comece com uma pilha vazia de frotas.
Para cada carro, calcule dist = target - position[i].
Se a pilha estiver vazia ou dist × topSpeed > topDist × speed[i], empilhe (dist, speed[i]); caso contrário, o carro se junta à frota do topo.
Retorne o tamanho da pilha.

def carFleet(target, position, speed):
    # Visit the cars from the one closest to the target backward.
    order = sorted(range(len(position)), key=lambda i: position[i], reverse=True)
    # One entry per fleet: (distance, speed) of the car at its front, which sets its arrival time.
    stack = []
    for i in order:
        dist, spd = target - position[i], speed[i]
        # dist / spd > top_dist / top_spd, compared without division:
        # this car arrives after the fleet ahead, so it never catches it.
        if not stack or dist * stack[-1][1] > stack[-1][0] * spd:
            stack.append((dist, spd))
    return len(stack)

Armadilhas e casos extremos

Contar um empate exato como uma nova frota. Os carros nas milhas 8 e 2 do exemplo 1 alcançam a frota na milha 20 e se juntam a ela. Empilhe apenas quando o tempo for estritamente maior.
Estouro no produto cruzado. 10^6 × 10^6 = 10^12 não cabe em 32 bits: em Java, C, C++, C# e Rust, converta para 64 bits antes de multiplicar; em R, use números de ponto flutuante.
Ordenar na direção errada. Começar pelo carro mais distante do destino compara cada carro com os carros atrás dele, que nunca podem bloqueá-lo.
Ordenar apenas position. Ordene os índices ou os pares (position, speed) para que cada velocidade continue associada ao seu carro.

Perguntas frequentes3

Qual é a complexidade de tempo do Car Fleet?

Ordenar por posição leva O(n log n) e a passagem com uma pilha leva O(n), então o total é de O(n log n) de tempo e O(n) de memória. Verificar cada carro em relação a todos os carros à frente leva O(n²).

Por que Car Fleet usa uma pilha?

Ao percorrer os carros da frente para trás, cada carro novo só precisa ser comparado com a frota imediatamente à frente, a última formada. Uma pilha mantém essa frota no topo. Como só o topo é lido, duas variáveis também funcionam; a pilha ainda permite que você mantenha as próprias frotas.

Como comparar horários de chegada sem usar ponto flutuante?

O tempo de chegada é dist / speed. Como as velocidades são positivas, d1 / s1 > d2 / s2 é válido exatamente quando d1 × s2 > d2 × s1. Ambos os lados são inteiros de até 10^12, então calcule-os em um tipo de 64 bits; assim, a comparação é exata, sem necessidade de considerar arredondamentos.

def carFleet(target, position, speed):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumentos

target = 20
position = [14, 2, 8, 17, 0]
speed = [3, 6, 4, 1, 2]

Saída Esperada