Car Fleet

Q: Độ phức tạp thời gian của Car Fleet là bao nhiêu?

Sắp xếp theo vị trí mất O(n log n) , còn lượt xử lý bằng ngăn xếp mất O(n) , nên tổng thời gian là O(n log n) và bộ nhớ cần dùng là O(n) . Kiểm tra từng xe với mọi xe phía trước mất O(n²) .

Q: Làm thế nào để so sánh thời gian đến mà không dùng số thực?

Thời gian đến nơi là dist / speed . Vì tốc độ luôn dương, d1 / s1 > d2 / s2 đúng khi và chỉ khi d1 × s2 > d2 × s1 . Hai vế đều là số nguyên có giá trị tối đa 10^12 , vì vậy hãy tính chúng bằng kiểu dữ liệu 64 bit. Phép so sánh sẽ cho kết quả chính xác, không cần xét đến việc làm tròn.

Trung bìnhNgăn xếp Sắp xếp

+10

Các xe chạy trên một con đường một làn hướng đến cột mốc target. Xe i bắt đầu ở cột mốc position[i] và chạy với tốc độ speed[i] dặm một giờ. Không xe nào có thể vượt xe khác: xe đuổi kịp một xe chạy chậm hơn sẽ đi ngay phía sau xe đó, và từ đó hai xe di chuyển cùng nhau với tốc độ chậm hơn như một đoàn xe.

Một xe riêng lẻ cũng là một đoàn xe, và xe đến đúng lúc đoàn xe tới đích sẽ gia nhập đoàn đó. Hãy trả về số đoàn xe đến đích.

Hàm

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

targetinteger: dặm mà mọi chiếc xe đều đang hướng tới
positioninteger-array: mốc đầu tiên trên đồng hồ quãng đường của mỗi chiếc xe
speedinteger-array: tốc độ của mỗi chiếc xe, tính bằng dặm một giờ
Trả vềinteger: số hạm đội đến được đích

Ràng buộc

n == position.length == speed.length
1 ≤ n ≤ 10⁴
1 ≤ target ≤ 10⁶
0 ≤ position[i] < target
1 ≤ speed[i] ≤ 10⁶
Tất cả các vị trí đều khác nhau.

Ví dụ

Đầu vào: target = 20position = [14, 2, 8, 17, 0]speed = [3, 6, 4, 1, 2]
Đầu ra: 2
Giải thích: Khi đi một mình, các xe ở dặm 17, 14, 8 và 2 cần lần lượt 3, 2, 3 và 3 giờ, nên xe ở dặm 14 đuổi kịp xe ở dặm 17, còn hai xe kia gặp họ tại dặm 20. Xe ở dặm 0 cần 10 giờ và đến nơi một mình.

Đầu vào: target = 9position = [0, 4, 7]speed = [1, 2, 3]
Đầu ra: 3
Giải thích: Các xe ở mốc 7, 4 và 0 dặm cần lần lượt 2/3, 5/2 và 9 giờ. Mỗi xe sẽ đến sau xe phía trước, nên không xe nào bắt kịp xe nào: 3 đoàn xe.

Câu hỏi mở rộng

Các vị trí là số nguyên (integer) nhỏ hơn target. Bạn có thể đếm số đoàn xe trong thời gian O(n + target) mà không cần dùng thuật toán sắp xếp dựa trên phép so sánh không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Trên cùng một làn đường, thứ tự các xe không bao giờ thay đổi. Yếu tố quyết định tất cả là thời điểm mỗi xe sẽ đến đích nếu đi một mình: (target - position[i]) / speed[i]. Xét các xe từ xe gần đích nhất trở về phía sau. Một xe chỉ tạo thành một đoàn xe mới khi nó đến đích muộn hơn hẳn đoàn xe phía trước.

Kiểm tra mọi chiếc xe phía trước

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Một chiếc xe dẫn đầu một đoàn xe khi và chỉ khi mọi chiếc xe phía trước nó đều đến sớm hơn nếu đi một mình. Nếu có chiếc xe phía trước nào đến không sớm hơn, xe của bạn sẽ bắt kịp nó hoặc đoàn xe của nó trước khi đến đích. Nếu tất cả đều đến sớm hơn, không chiếc xe nào phía trước có thể cản trở xe của bạn, vì đoàn xe đến đích vào thời điểm muộn nhất trong số các xe đi riêng lẻ. Hãy đếm số xe dẫn đầu bằng cách so sánh chính xác các thời gian qua phép nhân chéo.

Mỗi chiếc xe kiểm tra toàn bộ n chiếc xe: 10^8 lần kiểm tra khi n = 10^4.

Thuật toán

Đặt fleets = 0.
Với mỗi xe i, xét mọi xe j có position[j] > position[i].
Nếu có j thỏa mãn (target - position[j]) × speed[i] ≥ (target - position[i]) × speed[j], xe i bị bắt kịp: bỏ qua xe đó.
Nếu không, xe i dẫn đầu một nhóm xe: tăng fleets thêm 1.
Trả về 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

Sắp xếp theo vị trí và xếp chồng các hạm đội

Ý tưởng

Sắp xếp theo vị trí, xe gần đích nhất đứng trước, những xe phía trước xe hiện tại chính là các xe đã được xét và đã nằm trong các đoàn xe. Lưu các đoàn xe trên một ngăn xếp, mỗi phần tử chứa khoảng cách và tốc độ của xe dẫn đầu, yếu tố quyết định thời gian đoàn xe đến nơi.

Chỉ cần quan tâm đến phần tử trên cùng. Mỗi lần thêm vào, thời gian đến của đoàn xe phải muộn hơn nghiêm ngặt so với đoàn xe bên dưới, vì vậy thời gian tăng dần từ dưới lên trên; nếu muộn hơn phần tử trên cùng thì cũng muộn hơn mọi xe phía trước.

Ví dụ 1, các xe theo thứ tự nằm ở vị trí 17, 14, 8, 2 và 0, với khoảng cách chia cho tốc độ lần lượt là 3/1, 6/3, 12/4, 18/6, 20/2. Thêm (3, 1) vào ngăn xếp. Xe ở vị trí 14 nhập đoàn, vì 6 × 1 > 3 × 3 sai. Xe ở vị trí 8 có thời gian bằng nhau, 12 × 1 = 3 × 4, nên nhập đoàn; xe ở vị trí 2 cũng vậy. Với xe ở vị trí 0, 20 × 1 > 3 × 2: thêm vào ngăn xếp.

Thuật toán

Sắp xếp chỉ số của các xe theo vị trí, từ lớn nhất đến nhỏ nhất.
Bắt đầu với một ngăn xếp đội xe trống.
Với mỗi xe, tính dist = target - position[i].
Nếu ngăn xếp trống hoặc dist × topSpeed > topDist × speed[i], hãy thêm (dist, speed[i]) vào ngăn xếp; nếu không, xe sẽ nhập vào đội xe trên cùng.
Trả về kích thước của ngăn xếp.

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)

Lỗi thường gặp và trường hợp biên

Tính trường hợp hòa chính xác là một đội xe mới. Các xe ở dặm 8 và 2 trong ví dụ 1 gặp đội xe tại dặm 20 và nhập vào đội đó. Chỉ thêm vào khi thời gian đến muộn hơn hẳn.
Tràn số khi tính tích chéo. 10^6 × 10^6 = 10^12 vượt quá giới hạn 32 bit: trong Java, C, C++, C# và Rust, hãy chuyển sang 64 bit trước khi nhân; trong R, hãy dùng số thực.
Sắp xếp sai chiều. Bắt đầu từ xe xa đích nhất sẽ khiến bạn so sánh mỗi xe với các xe phía sau nó, vốn không thể cản xe đó.
Chỉ sắp xếp position. Hãy sắp xếp các chỉ số hoặc các cặp (position, speed) để mỗi tốc độ vẫn đi cùng xe tương ứng.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Car Fleet là bao nhiêu?

Sắp xếp theo vị trí mất O(n log n), còn lượt xử lý bằng ngăn xếp mất O(n), nên tổng thời gian là O(n log n) và bộ nhớ cần dùng là O(n). Kiểm tra từng xe với mọi xe phía trước mất O(n²).

Tại sao Car Fleet sử dụng ngăn xếp?

Khi duyệt các xe từ phía trước, mỗi xe mới chỉ cần được so sánh với đội xe ngay phía trước, đội được hình thành gần nhất. Ngăn xếp giữ đội xe đó ở trên cùng. Vì chỉ đọc phần tử trên cùng nên dùng hai biến cũng được; ngăn xếp còn giúp bạn lưu lại chính các đội xe.

Làm thế nào để so sánh thời gian đến mà không dùng số thực?

Thời gian đến nơi là dist / speed. Vì tốc độ luôn dương, d1 / s1 > d2 / s2 đúng khi và chỉ khi d1 × s2 > d2 × s1. Hai vế đều là số nguyên có giá trị tối đa 10^12, vì vậy hãy tính chúng bằng kiểu dữ liệu 64 bit. Phép so sánh sẽ cho kết quả chính xác, không cần xét đến việc làm tròn.

def carFleet(target, position, speed):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

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

Đầu ra mong đợi