Car Fleet

Q: Apa kompleksitas waktu Car Fleet?

Mengurutkan berdasarkan posisi membutuhkan waktu O(n log n) dan proses dengan stack membutuhkan waktu O(n) , sehingga total waktunya O(n log n) dan memorinya O(n) . Memeriksa setiap mobil terhadap setiap mobil di depannya membutuhkan waktu O(n²) .

Q: Bagaimana cara membandingkan waktu kedatangan tanpa bilangan floating point?

Waktu tiba adalah dist / speed . Karena kecepatannya positif, d1 / s1 > d2 / s2 berlaku tepat ketika d1 × s2 > d2 × s1 . Kedua sisi berupa bilangan bulat hingga 10^12 , jadi hitung keduanya dengan tipe 64-bit dan perbandingannya akurat, tanpa perlu mempertimbangkan pembulatan.

SedangStack Pengurutan

+10

Mobil melaju di jalan satu lajur menuju mil target. Mobil i mulai di mil position[i] dan melaju dengan kecepatan speed[i] mil per jam. Mobil tidak dapat mendahului mobil lain: mobil yang menyusul mobil yang lebih lambat akan tetap tepat di belakangnya, dan setelah itu keduanya bergerak bersama dengan kecepatan yang lebih lambat sebagai satu armada.

Satu mobil juga merupakan armada, dan mobil yang tepat mencapai armada di tujuan akan bergabung dengannya. Kembalikan jumlah armada yang tiba di tujuan.

Fungsi

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

targetinteger: jarak satu mil yang dituju setiap mobil
positioninteger-array: mile awal setiap mobil
speedinteger-array: kecepatan setiap mobil, dalam mil per jam
Mengembalikaninteger: jumlah armada yang mencapai tujuan

Batasan

n == position.length == speed.length
1 ≤ n ≤ 10⁴
1 ≤ target ≤ 10⁶
0 ≤ position[i] < target
1 ≤ speed[i] ≤ 10⁶
Semua posisi berbeda.

Contoh

Input: target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
Output: 2
Penjelasan: Sendirian, mobil-mobil di mil 17, 14, 8, dan 2 membutuhkan waktu 3, 2, 3, dan 3 jam, jadi mobil di mil 14 menyusul mobil di mil 17, sedangkan dua mobil lainnya mencapai mereka di mil 20. Mobil di mil 0 membutuhkan waktu 10 jam dan tiba sendirian.

Input: target = 9position = [0, 4, 7]speed = [1, 2, 3]
Output: 3
Penjelasan: Mobil-mobil pada jarak 7, 4, dan 0 membutuhkan waktu 2/3, 5/2, dan 9 jam. Masing-masing akan tiba setelah mobil di depannya, jadi tidak ada yang menyusul mobil lain: 3 armada.

Pertanyaan lanjutan

Posisinya adalah bilangan bulat di bawah target. Bisakah kamu menghitung armada dalam waktu O(n + target), tanpa pengurutan perbandingan?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Di satu jalur, urutan mobil tidak pernah berubah, dan yang menentukan semuanya adalah waktu yang dibutuhkan setiap mobil untuk tiba jika berjalan sendiri: (target - position[i]) / speed[i]. Kunjungi mobil mulai dari yang paling dekat dengan tujuan, lalu bergerak ke belakang. Sebuah mobil memulai armada baru hanya jika waktu tibanya benar-benar lebih lama daripada armada di depannya.

Periksa setiap mobil di depan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Sebuah mobil memimpin armada tepat ketika setiap mobil di depannya akan tiba lebih awal jika berjalan sendiri. Jika ada mobil di depannya yang tiba pada waktu yang sama atau lebih lambat, mobilmu akan menyusul mobil itu, atau armadanya, sebelum mencapai tujuan. Jika semua tiba lebih awal, tidak ada apa pun di depan yang bisa menghambatnya, karena armada tiba pada waktu paling lambat di antara waktu tempuh mobil-mobilnya jika berjalan sendiri. Hitung mobil yang memimpin dengan membandingkan waktu secara tepat melalui perkalian silang.

Setiap mobil memeriksa semua n mobil: 10^8 pemeriksaan untuk n = 10^4.

Algoritma

Tetapkan fleets = 0.
Untuk setiap mobil i, periksa setiap mobil j dengan position[j] > position[i].
Jika ada j yang memenuhi (target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j], mobil i tertangkap: lewati.
Jika tidak, mobil i memimpin sebuah kelompok mobil: tambahkan 1 ke fleets.
Kembalikan 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

Urutkan berdasarkan posisi dan susun armada

Intuisi

Diurutkan berdasarkan posisi, dengan yang paling dekat ke tujuan berada lebih dulu, mobil di depan mobil saat ini adalah tepat mobil-mobil yang sudah terlihat dan sudah tergabung dalam armada. Simpan armada di dalam stack, masing-masing sebagai jarak dan kecepatan mobil terdepannya, yang menentukan waktu kedatangan armada.

Yang penting hanya bagian teratas. Setiap penambahan tiba secara ketat lebih lambat daripada armada di bawahnya, jadi waktunya meningkat dari bawah ke atas, dan waktu yang lebih lambat daripada bagian teratas berarti lebih lambat daripada setiap mobil di depan.

Contoh 1, urutannya adalah mobil-mobil di posisi 17, 14, 8, 2, dan 0, dengan jarak dibagi kecepatan 3/1, 6/3, 12/4, 18/6, 20/2. Tambahkan (3, 1). Mobil di posisi 14 bergabung, karena 6 × 1 > 3 × 3 bernilai salah. Mobil di posisi 8 tiba bersamaan, 12 × 1 = 3 × 4, lalu bergabung, begitu juga mobil di posisi 2. Untuk mobil di posisi 0, 20 × 1 > 3 × 2: tambahkan.

Algoritma

Urutkan indeks mobil berdasarkan posisinya, dari yang terbesar.
Mulai dengan stack armada yang kosong.
Untuk setiap mobil, hitung dist = target - position[i].
Jika stack kosong atau dist × topSpeed > topDist × speed[i], dorong (dist, speed[i]) ke stack; jika tidak, mobil tersebut bergabung dengan armada teratas.
Kembalikan ukuran 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)

Jebakan dan kasus tepi

Menghitung kemacetan seri sebagai armada baru. Mobil pada mil 8 dan 2 dalam contoh 1 bertemu dengan armada pada mil 20 dan bergabung dengannya. Lakukan push hanya jika waktunya benar-benar lebih lama.
Overflow pada hasil kali silang. 10^6 × 10^6 = 10^12 tidak muat dalam 32 bit: di Java, C, C++, C# dan Rust, ubah ke 64 bit sebelum mengalikan; di R, gunakan bilangan double.
Mengurutkan dengan arah yang salah. Memulai dari mobil yang paling jauh dari tujuan berarti membandingkan setiap mobil dengan mobil di belakangnya, yang tidak mungkin menghalanginya.
Mengurutkan position saja. Urutkan indeks atau pasangan (position, speed), agar setiap speed tetap berpasangan dengan mobilnya.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu Car Fleet?

Mengurutkan berdasarkan posisi membutuhkan waktu O(n log n) dan proses dengan stack membutuhkan waktu O(n), sehingga total waktunya O(n log n) dan memorinya O(n). Memeriksa setiap mobil terhadap setiap mobil di depannya membutuhkan waktu O(n²).

Mengapa Car Fleet menggunakan stack?

Jika menelusuri mobil dari depan, setiap mobil baru hanya perlu dibandingkan dengan armada tepat di depannya, yaitu armada yang terakhir terbentuk. Stack menyimpan armada tersebut di bagian atas. Karena hanya bagian atas yang dibaca, dua variabel juga bisa digunakan; stack juga menyimpan armada itu sendiri untukmu.

Bagaimana cara membandingkan waktu kedatangan tanpa bilangan floating point?

Waktu tiba adalah dist / speed. Karena kecepatannya positif, d1 / s1 > d2 / s2 berlaku tepat ketika d1 × s2 > d2 × s1. Kedua sisi berupa bilangan bulat hingga 10^12, jadi hitung keduanya dengan tipe 64-bit dan perbandingannya akurat, tanpa perlu mempertimbangkan pembulatan.

def carFleet(target, position, speed):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan