Car Fleet

Q: Jaka jest złożoność czasowa problemu Car Fleet?

Sortowanie według pozycji zajmuje O(n log n) , a przebieg ze stosem zajmuje O(n) , więc łączna złożoność czasowa wynosi O(n log n) , a pamięciowa O(n) . Sprawdzanie każdego samochodu względem każdego samochodu przed nim zajmuje O(n²) .

Q: Jak porównywać czasy przybycia bez użycia liczb zmiennoprzecinkowych?

Czas przybycia to dist / speed . Ponieważ prędkości są dodatnie, d1 / s1 > d2 / s2 zachodzi dokładnie wtedy, gdy d1 × s2 > d2 × s1 . Obie strony są liczbami całkowitymi nie większymi niż 10^12 , więc oblicz je w typie 64-bitowym, a porównanie będzie dokładne i nie trzeba będzie rozważać zaokrągleń.

ŚrednieStos Sortowanie

+10

Samochody jadą jednokierunkową drogą w stronę mili target. Samochód i rozpoczyna jazdę na mili position[i] i porusza się z prędkością speed[i] mil na godzinę. Żaden samochód nie może wyprzedzić innego: samochód, który dogoni wolniejszy pojazd, pozostaje tuż za nim, a od tej chwili oba poruszają się razem z mniejszą prędkością jako jedna kolumna.

Pojedynczy samochód również tworzy kolumnę, a samochód, który dogoni kolumnę dokładnie w miejscu docelowym, dołącza do niej. Zwróć liczbę kolumn, które docierają do celu.

Funkcja

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

targetinteger: mila, do której zmierza każdy samochód
positioninteger-array: początkowy przebieg każdego samochodu
speedinteger-array: prędkość każdego samochodu, w milach na godzinę
Zwracainteger: liczba flot, które docierają do celu

Ograniczenia

n == position.length == speed.length
1 ≤ n ≤ 10⁴
1 ≤ target ≤ 10⁶
0 ≤ position[i] < target
1 ≤ speed[i] ≤ 10⁶
Wszystkie pozycje są różne.

Przykłady

Wejście: target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
Wyjście: 2
Wyjaśnienie: Samochody znajdujące się na milach 17, 14, 8 i 2 potrzebują odpowiednio 3, 2, 3 i 3 godzin, więc samochód z mili 14 dogania samochód z mili 17, a dwa pozostałe docierają do nich na mili 20. Samochód z mili 0 potrzebuje 10 godzin i dociera sam.

Wejście: target = 9position = [0, 4, 7]speed = [1, 2, 3]
Wyjście: 3
Wyjaśnienie: Samochody na milach 7, 4 i 0 potrzebują odpowiednio 2/3, 5/2 i 9 godzin. Każdy z nich dotarłby na miejsce po samochodzie jadącym przed nim, więc żaden nie dogoni żadnego innego: 3 floty.

Pytanie dodatkowe

Pozycje są liczbami całkowitymi mniejszymi od target. Czy potrafisz policzyć floty w czasie O(n + target), bez sortowania przez porównania?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Na jednym pasie samochody nigdy nie zmieniają kolejności, a o wszystkim decyduje to, kiedy każdy samochód dotarłby samodzielnie: (target - position[i]) / speed[i]. Rozpatruj samochody od tego najbliższego celowi do najdalszego. Samochód rozpoczyna nową grupę tylko wtedy, gdy dotarłby do celu ściśle później niż grupa przed nim.

Sprawdź każdy samochód przed tobą

Poprawne, ale nie kończy się na największych testach

Intuicja

Samochód prowadzi flotę dokładnie wtedy, gdy każdy samochód przed nim dotarłby samodzielnie ściśle wcześniej. Jeśli któryś samochód przed nim dotarłby nie wcześniej, Twój samochód dogoni go lub jego flotę przed dotarciem do celu. Jeśli wszystkie dotarłyby wcześniej, nic z przodu nie może go spowolnić, ponieważ flota dociera do celu w najpóźniejszym czasie, w którym dotarłby samodzielnie któryś z jej samochodów. Policz samochody prowadzące, porównując czasy dokładnie przez mnożenie na krzyż.

Każdy samochód sprawdza wszystkie n samochodów: 10^8 sprawdzeń dla n = 10^4.

Algorytm

Ustaw fleets = 0.
Dla każdego samochodu i sprawdź każdy samochód j, dla którego position[j] > position[i].
Jeśli dla któregoś j zachodzi (target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j], samochód i zostaje dogoniony: pomiń go.
W przeciwnym razie samochód i przewodzi kolumnie: zwiększ fleets o 1.
Zwróć 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

Sortuj według pozycji i układaj floty w stos

Intuicja

Posortowane według pozycji, od najbliższego celu, samochody przed aktualnym to dokładnie te, które już widzieliśmy, już należące do flot. Przechowuj floty na stosie, każdą jako odległość i prędkość jej czołowego samochodu, które wyznaczają czas przyjazdu floty.

Liczy się tylko wierzchołek. Każdy dodany element dociera ściśle później niż flota poniżej, więc czasy rosną od dołu do góry, a później niż wierzchołek oznacza później niż każdy samochód z przodu.

W przykładzie 1 samochody w kolejności znajdują się na pozycjach 17, 14, 8, 2 i 0, a ich stosunki odległości do prędkości to 3/1, 6/3, 12/4, 18/6, 20/2. Dodaj (3, 1). Samochód na pozycji 14 dołącza, ponieważ 6 × 1 > 3 × 3 jest fałszem. Samochód na pozycji 8 zrównuje się, 12 × 1 = 3 × 4, i dołącza; tak samo samochód na pozycji 2. W przypadku samochodu na pozycji 0, 20 × 1 > 3 × 2: dodaj na stos.

Algorytm

Posortuj indeksy samochodów według pozycji, od największej do najmniejszej.
Zacznij od pustego stosu flot.
Dla każdego samochodu oblicz dist = target - position[i].
Jeśli stos jest pusty lub dist × topSpeed > topDist × speed[i], dodaj (dist, speed[i]) na stos; w przeciwnym razie samochód dołącza do floty na szczycie stosu.
Zwróć rozmiar stosu.

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)

Pułapki i przypadki brzegowe

Liczenie dokładnego remisu jako nowej floty. Samochody na milach 8 i 2 w przykładzie 1 dołączają do floty na mili 20. Dodawaj samochód tylko wtedy, gdy jego czas jest ściśle późniejszy.
Przepełnienie przy mnożeniu krzyżowym. 10^6 × 10^6 = 10^12 nie mieści się w 32 bitach: w Javie, C, C++, C# i Rust przed mnożeniem rozszerz typ do 64 bitów; w R używaj liczb zmiennoprzecinkowych.
Sortowanie w niewłaściwym kierunku. Rozpoczynając od samochodu najdalej od celu, porównujesz każdy samochód z samochodami jadącymi za nim, które nigdy nie mogą go zablokować.
Sortowanie samego position. Sortuj indeksy albo pary (position, speed), aby każda prędkość pozostała przypisana do swojego samochodu.

Najczęstsze pytania3

Jaka jest złożoność czasowa problemu Car Fleet?

Sortowanie według pozycji zajmuje O(n log n), a przebieg ze stosem zajmuje O(n), więc łączna złożoność czasowa wynosi O(n log n), a pamięciowa O(n). Sprawdzanie każdego samochodu względem każdego samochodu przed nim zajmuje O(n²).

Dlaczego Car Fleet używa stosu?

Odwiedzając samochody od przodu, każdy nowy samochód trzeba porównać tylko z flotą bezpośrednio przed nim, tą utworzoną jako ostatnia. Stos utrzymuje tę flotę na wierzchu. Ponieważ odczytywany jest tylko element ze szczytu, wystarczą też dwie zmienne; stos pozwala ponadto zachować same floty.

Jak porównywać czasy przybycia bez użycia liczb zmiennoprzecinkowych?

Czas przybycia to dist / speed. Ponieważ prędkości są dodatnie, d1 / s1 > d2 / s2 zachodzi dokładnie wtedy, gdy d1 × s2 > d2 × s1. Obie strony są liczbami całkowitymi nie większymi niż 10^12, więc oblicz je w typie 64-bitowym, a porównanie będzie dokładne i nie trzeba będzie rozważać zaokrągleń.

def carFleet(target, position, speed):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

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

Oczekiwany wynik