Car Fleet

Q: Quelle est la complexité temporelle de Car Fleet ?

Le tri par position prend O(n log n) et le parcours avec une pile prend O(n) , donc la complexité totale est de O(n log n) en temps et de O(n) en mémoire. Comparer chaque voiture à toutes celles qui la précèdent prend O(n²) .

Q: Comment comparer les heures d’arrivée sans virgule flottante ?

Un temps d’arrivée est égal à dist / speed . Comme les vitesses sont positives, d1 / s1 > d2 / s2 est vrai exactement lorsque d1 × s2 > d2 × s1 . Les deux côtés sont des entiers pouvant atteindre 10^12 ; calcule-les donc avec un type 64 bits. La comparaison est ainsi exacte, sans avoir à tenir compte des arrondis.

MoyenPile Tri

+10

Des voitures roulent sur une route à une seule voie vers le point kilométrique target. La voiture i démarre au point kilométrique position[i] et roule à speed[i] miles par heure. Aucune voiture ne peut en dépasser une autre : une voiture qui rattrape une voiture plus lente reste juste derrière elle et, dès lors, les deux avancent ensemble à la vitesse la plus lente, formant une seule flotte.

Une voiture seule constitue aussi une flotte, et une voiture qui rejoint une flotte exactement à destination s’y intègre. Retournez le nombre de flottes qui arrivent à destination.

Fonction

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

targetinteger: le mile vers lequel se dirigent toutes les voitures
positioninteger-array: le kilométrage initial de chaque voiture
speedinteger-array: la vitesse de chaque voiture, en miles par heure
Renvoieinteger: le nombre de flottes qui atteignent la destination

Contraintes

n == position.length == speed.length
1 ≤ n ≤ 10⁴
1 ≤ target ≤ 10⁶
0 ≤ position[i] < target
1 ≤ speed[i] ≤ 10⁶
Toutes les positions sont différentes.

Exemples

Entrée: target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
Sortie: 2
Explication: Seules, les voitures aux miles 17, 14, 8 et 2 ont besoin de 3, 2, 3 et 3 heures ; la voiture à 14 rattrape donc celle à 17, et les deux autres les rejoignent au mile 20. La voiture à 0 a besoin de 10 heures et arrive seule.

Entrée: target = 9position = [0, 4, 7]speed = [1, 2, 3]
Sortie: 3
Explication: Les voitures aux miles 7, 4 et 0 ont besoin de 2/3, 5/2 et 9 heures. Chacune arriverait après la voiture qui la précède, donc personne ne rattrape personne : 3 flottes.

Pour aller plus loin

Les positions sont des entiers inférieurs à target. Peux-tu compter les flottes en O(n + target), sans tri par comparaison ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Sur une même voie, les voitures ne changent jamais d’ordre, et tout dépend du moment où chaque voiture arriverait seule : (target - position[i]) / speed[i]. Parcourez les voitures en partant de celle qui est la plus proche de la destination et en remontant. Une voiture ne forme une nouvelle flotte que si elle arriverait strictement plus tard que la flotte qui la précède.

Vérifiez chaque voiture devant vous

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Une voiture est à la tête d’une flotte exactement lorsque chaque voiture devant elle arriverait seule strictement plus tôt. Si une voiture devant elle n’arrivait pas plus tôt, votre voiture la rattraperait, ou rattraperait sa flotte, avant la destination. Si elles arrivent toutes plus tôt, rien devant ne peut la ralentir, car une flotte arrive au moment où arrive seule la voiture la plus lente. Comptez les voitures de tête en comparant les temps exactement par produit en croix.

Chaque voiture parcourt les n voitures : 10^8 vérifications pour n = 10^4.

Algorithme

Définissez fleets = 0.
Pour chaque voiture i, examinez chaque voiture j telle que position[j] > position[i].
Si un certain j vérifie (target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j], la voiture i est rattrapée : ignorez-la.
Sinon, la voiture i mène une flotte : ajoutez 1 à fleets.
Renvoyez 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

Trier par position et empiler les flottes

Intuition

Triées par position, la plus proche de la destination en premier, les voitures devant celle actuelle sont exactement celles déjà vues, déjà dans des flottes. Gardez les flottes sur une pile, chacune stockée sous la forme de la distance et de la vitesse de sa voiture de tête, qui détermine le temps d’arrivée de la flotte.

Seul le sommet compte. Chaque élément ajouté arrive strictement plus tard que la flotte en dessous, donc les temps augmentent du bas vers le haut, et arriver plus tard que le sommet signifie arriver plus tard que toutes les voitures devant.

Dans l’exemple 1, l’ordre est celui des voitures aux positions 17, 14, 8, 2 et 0, avec les rapports distance sur vitesse 3/1, 6/3, 12/4, 18/6, 20/2. Empilez (3, 1). La voiture à 14 rejoint la flotte, car 6 × 1 > 3 × 3 est faux. La voiture à 8 arrive à égalité, 12 × 1 = 3 × 4, et rejoint la flotte, tout comme celle à 2. Pour la voiture à 0, 20 × 1 > 3 × 2 : empilez-la.

Algorithme

Triez les indices des voitures par position, de la plus grande à la plus petite.
Commencez avec une pile de flottes vide.
Pour chaque voiture, calculez dist = target - position[i].
Si la pile est vide ou si dist × topSpeed > topDist × speed[i], empilez (dist, speed[i]) ; sinon, la voiture rejoint la flotte au sommet.
Renvoyez la taille de la pile.

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)

Pièges et cas limites

Compter une égalité exacte comme un nouveau convoi. Les voitures situées aux miles 8 et 2 dans l’exemple 1 rejoignent le convoi au mile 20. Empilez uniquement si le temps est strictement supérieur.
Débordement dans le produit croisé. 10^6 × 10^6 = 10^12 ne tient pas sur 32 bits : en Java, C, C++, C# et Rust, passez à 64 bits avant la multiplication ; en R, utilisez des nombres à virgule flottante.
Trier dans le mauvais sens. En partant de la voiture la plus éloignée de la destination, on compare chaque voiture à celles qui sont derrière elle, qui ne peuvent jamais la bloquer.
Trier position seule. Triez les index ou les paires (position, vitesse), afin que chaque vitesse reste associée à sa voiture.

Questions fréquentes3

Quelle est la complexité temporelle de Car Fleet ?

Le tri par position prend O(n log n) et le parcours avec une pile prend O(n), donc la complexité totale est de O(n log n) en temps et de O(n) en mémoire. Comparer chaque voiture à toutes celles qui la précèdent prend O(n²).

Pourquoi Car Fleet utilise-t-il une pile ?

En parcourant les voitures depuis l’avant, chaque nouvelle voiture n’a qu’à être comparée à la flotte juste devant, celle formée en dernier. Une pile maintient cette flotte au sommet. Comme seul le sommet est consulté, deux variables conviennent aussi ; la pile vous laisse également les flottes elles-mêmes.

Comment comparer les heures d’arrivée sans virgule flottante ?

Un temps d’arrivée est égal à dist / speed. Comme les vitesses sont positives, d1 / s1 > d2 / s2 est vrai exactement lorsque d1 × s2 > d2 × s1. Les deux côtés sont des entiers pouvant atteindre 10^12 ; calcule-les donc avec un type 64 bits. La comparaison est ainsi exacte, sans avoir à tenir compte des arrondis.

def carFleet(target, position, speed):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu