Car Fleet

Q: Qual è la complessità temporale di Car Fleet?

L'ordinamento per posizione richiede O(n log n) e il passaggio con uno stack richiede O(n) , quindi il totale è O(n log n) di tempo e O(n) di memoria. Confrontare ogni auto con tutte quelle che la precedono richiede O(n²) .

Q: Come si confrontano gli orari di arrivo senza usare numeri in virgola mobile?

Il tempo di arrivo è dist / speed . Poiché le velocità sono positive, d1 / s1 > d2 / s2 vale esattamente quando d1 × s2 > d2 × s1 . Entrambi i membri sono numeri interi fino a 10^12 , quindi calcolali con un tipo a 64 bit e il confronto è esatto, senza arrotondamenti da considerare.

MedioStack Ordinamento

+10

Le auto percorrono una strada a una sola corsia verso il miglio target. L'auto i parte dal miglio position[i] e viaggia a speed[i] miglia orarie. Nessuna auto può sorpassarne un'altra: un'auto che raggiunge un'altra più lenta le resta subito dietro e, da quel momento, le due auto procedono insieme alla velocità più lenta, formando un'unica flotta.

Anche una sola auto costituisce una flotta e un'auto che raggiunge una flotta esattamente alla destinazione si unisce a essa. Restituisci il numero di flotte che arrivano a destinazione.

Funzione

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

targetinteger: il miglio verso cui sono dirette tutte le auto
positioninteger-array: il miglio di partenza di ogni auto
speedinteger-array: la velocità di ogni auto, in miglia all’ora
Restituisceinteger: il numero di flotte che raggiungono la destinazione

Vincoli

n == position.length == speed.length
1 ≤ n ≤ 10⁴
1 ≤ target ≤ 10⁶
0 ≤ position[i] < target
1 ≤ speed[i] ≤ 10⁶
Tutte le posizioni sono diverse.

Esempi

Input: target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
Output: 2
Spiegazione: Da soli, le auto ai miglia 17, 14, 8 e 2 impiegano rispettivamente 3, 2, 3 e 3 ore, quindi quella al miglio 14 raggiunge quella al miglio 17 e le altre due le raggiungono al miglio 20. L’auto al miglio 0 impiega 10 ore e arriva da sola.

Input: target = 9position = [0, 4, 7]speed = [1, 2, 3]
Output: 3
Spiegazione: Le auto ai chilometri 7, 4 e 0 impiegano rispettivamente 2/3, 5/2 e 9 ore. Ognuna arriverebbe dopo l'auto che la precede, quindi nessuna raggiunge un'altra: 3 flotte.

Per approfondire

Le posizioni sono numeri interi minori di target. Riesci a contare le flotte in tempo O(n + target), senza un ordinamento per confronto?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Su una corsia, l’ordine delle auto non cambia mai e tutto dipende da quando arriverebbe ogni auto da sola: (target - position[i]) / speed[i]. Esamina le auto partendo da quella più vicina alla destinazione e procedendo all’indietro. Un’auto inizia una nuova flotta solo se arriverebbe strettamente dopo la flotta che la precede.

Controlla ogni auto davanti a te

Corretto, ma non termina sui test più grandi

Intuizione

Un'auto guida una flotta esattamente quando ogni auto davanti a essa arriverebbe da sola strettamente prima. Se un'auto davanti arriverebbe non prima, la tua auto la raggiunge, o raggiunge la sua flotta, prima della destinazione. Se tutte arrivano prima, nulla davanti può rallentarla, perché una flotta arriva al tempo più tardivo tra quelli delle sue auto considerate singolarmente. Conta le auto che guidano una flotta, confrontando i tempi esattamente tramite moltiplicazione incrociata.

Ogni auto esamina tutte le n auto: 10^8 controlli per n = 10^4.

Algoritmo

Imposta fleets = 0.
Per ogni auto i, esamina ogni auto j con position[j] > position[i].
Se esiste un j tale che (target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j], l’auto i viene raggiunta: saltala.
Altrimenti, l’auto i guida una flotta: aggiungi 1 a fleets.
Restituisci 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

Ordina per posizione e impila le flotte

Intuizione

Ordinando per posizione, con prima quella più vicina alla destinazione, le auto che precedono quella attuale sono esattamente quelle già viste, già nei convogli. Tieni i convogli in una pila, ciascuno rappresentato dalla distanza e dalla velocità della sua auto di testa, che determina il tempo di arrivo del convoglio.

Conta solo la cima. Ogni elemento inserito arriva strettamente dopo il convoglio sottostante, quindi i tempi aumentano dal basso verso l'alto; un tempo successivo a quello della cima è successivo a quello di tutte le auto davanti.

Nell'esempio 1, in ordine, le auto si trovano a 17, 14, 8, 2 e 0, con distanza divisa per velocità pari a 3/1, 6/3, 12/4, 18/6, 20/2. Inserisci (3, 1). L'auto a 14 si unisce, perché 6 × 1 > 3 × 3 è falso. L'auto a 8 arriva nello stesso momento, 12 × 1 = 3 × 4, e si unisce; lo stesso vale per l'auto a 2. Per l'auto a 0, 20 × 1 > 3 × 2: inseriscila.

Algoritmo

Ordina gli indici delle auto per posizione, dalla più alta alla più bassa.
Inizia con uno stack vuoto di flotte.
Per ogni auto, calcola dist = target - position[i].
Se lo stack è vuoto o dist × topSpeed > topDist × speed[i], inserisci (dist, speed[i]); altrimenti l’auto si unisce alla flotta in cima.
Restituisci la dimensione dello stack.

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)

Trappole e casi limite

Contare un pareggio esatto come una nuova flotta. Le auto ai chilometri 8 e 2 nell'esempio 1 raggiungono la flotta al chilometro 20 e si uniscono a essa. Aggiungi elementi solo quando il tempo è strettamente maggiore.
Overflow nel prodotto incrociato. 10^6 × 10^6 = 10^12 non entra in 32 bit: in Java, C, C++ e Rust, passa a 64 bit prima di moltiplicare; in R, usa i numeri double.
Ordinare nel verso sbagliato. Partire dall'auto più lontana dalla destinazione significa confrontare ogni auto con quelle dietro di essa, che non possono mai bloccarla.
Ordinare solo position. Ordina gli indici oppure le coppie (position, speed), così ogni velocità rimane associata alla sua auto.

Domande frequenti3

Qual è la complessità temporale di Car Fleet?

L'ordinamento per posizione richiede O(n log n) e il passaggio con uno stack richiede O(n), quindi il totale è O(n log n) di tempo e O(n) di memoria. Confrontare ogni auto con tutte quelle che la precedono richiede O(n²).

Perché Car Fleet usa uno stack?

Visitando le auto dal davanti, ogni nuova auto deve essere confrontata solo con la flotta immediatamente precedente, quella formata per ultima. Una pila mantiene quella flotta in cima. Poiché si legge solo l’elemento in cima, funzionano anche due variabili; la pila ti lascia inoltre le flotte stesse.

Come si confrontano gli orari di arrivo senza usare numeri in virgola mobile?

Il tempo di arrivo è dist / speed. Poiché le velocità sono positive, d1 / s1 > d2 / s2 vale esattamente quando d1 × s2 > d2 × s1. Entrambi i membri sono numeri interi fino a 10^12, quindi calcolali con un tipo a 64 bit e il confronto è esatto, senza arrotondamenti da considerare.

def carFleet(target, position, speed):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

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

Output atteso