Car Fleet: khi thời gian đến đích thu gọn simulation thành một lần quét stack

Bản năng đầu tiên khi gặp Car Fleet thường là simulation. Có các xe ở các vị trí khác nhau, di chuyển với tốc độ khác nhau về phía đích, và bạn muốn đếm xem bao nhiêu nhóm đến cùng nhau. Có vẻ như bạn nên bước qua từng đơn vị thời gian, cập nhật vị trí, kiểm tra va chạm. Cách đó đúng về mặt khái niệm nhưng sụp đổ hoàn toàn dưới constraints: target lên đến 10^6, n lên đến 10^5, và simulation theo từng bước thời gian là O(target * n) — khoảng 10^11 phép tính trong trường hợp xấu nhất.

Insight mở ra giải pháp hiệu quả là một phép thay thế: thay vì theo dõi vị trí xe tại mỗi thời điểm, hãy tính xem mỗi xe mất bao lâu để đến target nếu không bị cản trở. Hai xe hợp thành một đoàn khi và chỉ khi xe sau đến không muộn hơn xe trước. Xe trước đóng vai trò như một ceiling — xe sau hoặc bắt kịp tại hoặc trước target, hoặc không. Bạn không cần biết chúng gặp nhau ở đâu.

Sự thu gọn đó biến simulation thành một lần duyệt với stack.

Đề bài

Có n chiếc xe đang di chuyển về phía đích target trên một con đường một làn. Mỗi xe có vị trí xuất phát và tốc độ riêng; xe không thể vượt qua xe phía trước nhưng có thể bắt kịp và di chuyển song song với tốc độ của xe chậm hơn. Một car fleet là một hoặc nhiều xe di chuyển cùng nhau — xe bắt kịp một fleet ngay tại target vẫn được tính là một phần của fleet đó. Trả về số fleet đến được target. Đề gốc: LeetCode 853.

Ràng buộc:
- n == position.length == speed.length
- 1 <= n <= 10^5
- 0 < target <= 10^6
- 0 <= position[i] < target
- Tất cả giá trị của position là duy nhất.
- 0 < speed[i] <= 10^6

Constraints nói gì

n == position.length == speed.length, 1 <= n <= 10^5, 0 < target <= 10^6. Tất cả vị trí là duy nhất. Tất cả tốc độ đều dương.

Đảm bảo unique position quan trọng hơn vẻ ngoài của nó. Nghĩa là không có hai xe bắt đầu tại cùng dặm, nên bạn không bao giờ phải xử lý tie ở vạch xuất phát. Thứ tự sắp xếp sau khi zip và sort theo position luôn là thứ tự nghiêm ngặt.

n <= 10^5 loại trừ O(n^2). Bất kỳ giải pháp nào so sánh mọi cặp xe đều bị loại. Kích thước này gợi ý O(n log n), đúng là điểm sort đưa bạn đến.

Giới hạn tốc độ speed[i] <= 10^6 kết hợp với target <= 10^6 nghĩa là thời gian đến đích nằm trong phạm vi double mà không có vấn đề precision. Thời gian đến đích tối đa là (10^6 - 0) / 1 = 10^6 giờ — hoàn toàn trong phạm vi floating-point.

Approach 1: brute-force simulation

Brute force thực sự là bước qua từng đơn vị thời gian rời rạc. Tại mỗi tick, tiến mỗi xe thêm tốc độ của nó (clamped tại target). Nếu vị trí xe nào đạt hoặc vượt qua xe phía trước, chúng hợp nhất và nhóm mới đi với tốc độ tối thiểu.

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        # Ghép cặp và sort tăng dần theo position
        cars = sorted(zip(position, speed))
        n = len(cars)
 
        groups = [[pos, spd, i] for i, (pos, spd) in enumerate(cars)]
 
        # Bước qua từng đơn vị thời gian -- O(target * n), không khả thi với input lớn
        arrived = [False] * n
        fleet_map = list(range(n))  # fleet_map[i] = chỉ số fleet leader
 
        time = 0
        while not all(arrived):
            time += 1
            for g in groups:
                if not arrived[fleet_map[g[2]]]:
                    g[0] = min(g[0] + g[1], target)
 
            # Kiểm tra merge: scan trái sang phải (position tăng dần)
            for i in range(n - 1):
                if arrived[fleet_map[groups[i][2]]]:
                    continue
                for j in range(i + 1, n):
                    if groups[j][0] >= groups[i][0]:
                        if fleet_map[groups[j][2]] != fleet_map[groups[i][2]]:
                            old = fleet_map[groups[j][2]]
                            new = fleet_map[groups[i][2]]
                            for k in range(n):
                                if fleet_map[groups[k][2]] == old:
                                    fleet_map[groups[k][2]] = new
                            groups[j][1] = groups[i][1]
                    else:
                        break
 
            for g in groups:
                if g[0] >= target:
                    arrived[fleet_map[g[2]]] = True
 
        return len(set(fleet_map))

public class Solution {
    public int CarFleet(int target, int[] position, int[] speed) {
        int n = position.Length;
        var cars = new (int pos, int spd)[n];
        for (int i = 0; i < n; i++) cars[i] = (position[i], speed[i]);
        Array.Sort(cars, (a, b) => a.pos.CompareTo(b.pos));
 
        double[] pos = new double[n];
        double[] spd = new double[n];
        for (int i = 0; i < n; i++) { pos[i] = cars[i].pos; spd[i] = cars[i].spd; }
        int[] fleet = new int[n];
        for (int i = 0; i < n; i++) fleet[i] = i;
 
        bool[] done = new bool[n];
        int time = 0;
        while (true) {
            time++;
            for (int i = 0; i < n; i++)
                if (!done[fleet[i]])
                    pos[i] = Math.Min(pos[i] + spd[i], target);
 
            for (int i = 0; i < n - 1; i++) {
                if (done[fleet[i]]) continue;
                for (int j = i + 1; j < n; j++) {
                    if (pos[j] >= pos[i] && fleet[j] != fleet[i]) {
                        int old = fleet[j], nw = fleet[i];
                        for (int k = 0; k < n; k++)
                            if (fleet[k] == old) { fleet[k] = nw; spd[k] = spd[i]; }
                    } else if (pos[j] < pos[i]) break;
                }
            }
 
            bool allDone = true;
            for (int i = 0; i < n; i++)
                if (pos[i] >= target) done[fleet[i]] = true;
                else allDone = false;
            if (allDone) break;
        }
 
        var seen = new System.Collections.Generic.HashSet<int>(fleet);
        return seen.Count;
    }
}

Time: O(target * n). Tại mỗi bước thời gian bạn chạm mọi xe, và có thể cần đến target bước. Với target = 10^6 và n = 10^5, đó là 10^11 phép tính — hoàn toàn không khả thi.

Space: O(n) cho các mảng làm việc.

Brute force hữu ích vì nó làm cho quy tắc hợp nhất fleet trở nên cụ thể. Nhưng không ai dùng cái này thật. Nó tồn tại trong bài viết vì thấy tại sao nó thất bại giúp hiểu rõ điều gì mà giải pháp hiệu quả đang thực sự khai thác.

Approach 2: sort theo position, stack thời gian đến đích

Insight chính: xe tại position p với tốc độ s đến target sau (target - p) / s giờ nếu không bị cản. Việc nó có bị cản hay không phụ thuộc hoàn toàn vào xe ngay phía trước nó (trong thứ tự sorted, tức là xe gần target nhất tiếp theo) có đến trước không. Nếu xe phía trước đến sớm hơn (thời gian nhỏ hơn), nó đã đến rồi khi xe sau đến vị trí của nó — không có fleet. Nếu xe phía trước đến muộn hơn (thời gian lớn hơn), xe sau bắt kịp và chúng tạo thành một fleet.

Có một hướng quan trọng: bạn phải xử lý các xe từ gần-đích-nhất đến xa-nhất. Một xe chỉ có thể bị cản bởi xe giữa nó và đích, không phải xe phía sau nó. Xử lý front-to-back nghĩa là mỗi xe bạn xem đã giải quyết xong liệu nó dẫn đầu một fleet hay hợp nhất vào fleet phía trước.

Stack lưu trữ thời gian đến đích của các fleet leader gặp được cho đến nay. Khi xử lý một xe:

• Nếu thời gian đến đích của nó lớn hơn top của stack, nó không thể bắt kịp fleet phía trước. Nó là fleet leader mới. Push.
• Nếu thời gian đến đích bé hơn hoặc bằng top, nó sẽ bắt kịp fleet phía trước (tại hoặc trước target). Nó bị hấp thụ. Không làm gì.

Cuối cùng, chiều cao stack là số fleet.

class Solution:
    def carFleet(self, target: int, position: list[int], speed: list[int]) -> int:
        # Sort giảm dần theo position: xử lý gần-đích-nhất trước
        cars = sorted(zip(position, speed), reverse=True)
 
        stack = []  # thời gian đến đích của các fleet leader
 
        for pos, spd in cars:
            arrival = (target - pos) / spd
 
            # Xe này là fleet leader mới nếu không thể bắt kịp fleet phía trước
            if not stack or arrival > stack[-1]:
                stack.append(arrival)
            # Ngược lại (arrival <= stack[-1]): bị hấp thụ vào fleet phía trước
 
        return len(stack)

public class Solution {
    public int CarFleet(int target, int[] position, int[] speed) {
        int n = position.Length;
 
        // Zip và sort giảm dần theo position
        var cars = new (int pos, int spd)[n];
        for (int i = 0; i < n; i++) cars[i] = (position[i], speed[i]);
        Array.Sort(cars, (a, b) => b.pos.CompareTo(a.pos));
 
        var stack = new Stack<double>();
 
        foreach (var (pos, spd) in cars) {
            double arrival = (double)(target - pos) / spd;
 
            if (stack.Count == 0 || arrival > stack.Peek()) {
                stack.Push(arrival);
            }
            // arrival <= stack.Peek(): xe này hợp nhất vào fleet phía trước
        }
 
        return stack.Count;
    }
}

Time: O(n log n) — bị chi phối bởi sort. Linear scan với stack là O(n), mỗi push/peek là O(1).

Space: O(n) cho mảng đã sort và stack. Trong trường hợp xấu nhất (mỗi xe tạo fleet riêng), stack chứa n thời gian đến đích.

Trace tay: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]

Bước 1 — tính thời gian đến đích của mỗi xe:

pos=10, spd=2 -> arrival = (12-10)/2 = 1.0
pos=8,  spd=4 -> arrival = (12-8)/4  = 1.0
pos=5,  spd=1 -> arrival = (12-5)/1  = 7.0
pos=3,  spd=3 -> arrival = (12-3)/3  = 3.0
pos=0,  spd=1 -> arrival = (12-0)/1  = 12.0

Bước 2 — sort giảm dần theo position và xử lý:

Xe tại pos=8 có cùng thời gian đến đích với pos=10 — nó bắt kịp đúng tại dặm 12, điều mà bài toán nói rõ ràng vẫn tính là cùng fleet. Điều kiện <= trong phép so sánh xử lý trường hợp này.

Xe tại pos=3 đến sau 3 giờ. Fleet phía trước (gốc tại pos=5) đến sau 7 giờ. Ba giờ ít hơn bảy, nên pos=3 bắt kịp fleet pos=5 trước target. Chúng hợp nhất.

Ba phần tử stack còn lại: fleet 1.0-giờ (pos=10+pos=8), fleet 7.0-giờ (pos=5+pos=3), và xe đơn độc 12.0-giờ tại pos=0. Output: 3.

Các edge case thực sự quan trọng

Một xe duy nhất (n = 1): vòng lặp chạy một lần, stack rỗng khi vào, xe được push. Chiều dài stack là 1. Đúng.

Tất cả xe cùng tốc độ với position khác nhau: vì position là unique và tốc độ bằng nhau, (target - pos) / spd giảm nghiêm ngặt khi position tăng. Thời gian đến đích của mỗi xe lớn hơn xe phía trước nó. Mỗi xe là fleet leader mới. Output bằng n. Stack lấp đầy hoàn toàn.

Xe nhanh nhất gần đích nhất: ví dụ 3 từ bài toán. Xe tại pos=4, spd=1 đến sau 96 giờ. Xe tại pos=2, spd=2 đến sau 49 giờ. Xe tại pos=0, spd=4 đến sau 25 giờ. Xử lý từ gần nhất: push 96.0, rồi 49.0 không lớn hơn 96.0 nên bị hấp thụ, rồi 25.0 cũng không lớn hơn 96.0, cũng bị hấp thụ. Stack: [96.0]. Một fleet. Khớp với output mong đợi.

Hai xe, xe sau đến cùng lúc: điều kiện là arrival > stack[-1], nên equality kích hoạt nhánh else (hấp thụ). Bài toán nói nếu xe bắt kịp fleet tại dặm target thì vẫn tính. Đúng.

Tất cả position gần 0, target rất lớn: không có rủi ro overflow. Thời gian đến đích tối đa là target / 1 = 10^6, hoàn toàn an toàn với double.

Xe đã được sort giảm dần theo input: sort vẫn là O(n log n). Bạn không thể bỏ qua nó vì input đảm bảo unique position nhưng không đảm bảo thứ tự cụ thể nào.

Tại sao stack là monotone tăng dần

Sau lần quét, stack chứa thời gian đến đích theo thứ tự tăng nghiêm ngặt từ đáy lên đỉnh. Đáy là fleet gần target nhất (thời gian nhỏ nhất). Đỉnh là fleet chậm nhất, xa target nhất.

Tính chất monotone này không phải ngẫu nhiên — đó là invariant bạn duy trì. Bạn chỉ push khi thời gian đến đích mới lớn nghiêm ngặt hơn top hiện tại. Bất kỳ phần tử mới nào bạn push đều lớn hơn tất cả phần tử bên dưới nó. Stack là bản ghi về "các fleet leader mà không xe nào xa hơn có thể bắt kịp."

Pattern ở đây là monotone stack, nhưng một cái không cần pop bất cứ thứ gì. Mỗi phần tử ở lại một khi đã push. Kích thước stack là câu trả lời. Đây là degenerate monotone stack — đôi khi gọi là one-way monotone stack — vì bạn chỉ push, không bao giờ pop.

Cái tôi thực sự sẽ viết

Brute-force simulation không phải bước interview thực tế. Nó quá lộn xộn và thất bại rõ ràng. Tôi sẽ đi thẳng đến observation: sort giảm dần theo position, tính thời gian đến đích, chạy stack sweep. Code chỉ khoảng 8 dòng Python.

Một điều khiến người ta hay bị bẫy là hướng sort. Tăng dần là mặc định tự nhiên — bạn nghĩ "xử lý xe theo thứ tự từ xuất phát đến đích." Sai hướng. Bạn cần xử lý từ gần-đích-nhất đến xa-nhất, vì xe chỉ có thể bị cản bởi thứ gì đó giữa nó và vạch đích, không phải thứ gì đó phía sau nó. Sort giảm dần, hoặc sort tăng dần rồi duyệt ngược.

Điều thứ hai hay bị mắc là dấu so sánh. Bạn hấp thụ khi arrival <= top, không phải <. Thiếu trường hợp bằng nhau có nghĩa là vi phạm quy tắc của bài toán — "nếu xe bắt kịp fleet tại target, vẫn tính." Các xe có thời gian đến đích giống nhau phải thu gọn thành một fleet.

Trong interview, tôi sẽ viết giải pháp sort-plus-stack và giải thích thế này: "Thời gian đến đích tóm gọn mọi thứ về số phận của một xe. Hai xe tạo thành fleet khi và chỉ khi thời gian đến đích của xe sau không lớn hơn xe trước. Nên tôi sort theo position, tính thời gian đến đích, và scan front-to-back duy trì stack các fleet leader riêng biệt." Đó là toàn bộ lập luận. Mười giây để giải thích, tám dòng để viết.

Bảng so sánh

Vị trí trong series stack

Series stack cho đến nay đã bao gồm Valid Parentheses (khớp cấu trúc) và Evaluate Reverse Polish Notation (tích lũy operand). Car Fleet thêm pattern thứ ba: dùng stack không phải để theo dõi nesting hay values, mà để duy trì một monotone sequence và đếm độ dài của nó.

Trick thời gian đến đích là ý tưởng có thể chuyển giao chính. Bất cứ khi nào bạn có các đối tượng đua về phía một ranh giới, và đối tượng sau chỉ có thể bắt kịp đối tượng trước (không bao giờ vượt qua), bạn có thể thu gọn simulation thành một phép so sánh thời gian đến đích. Stack giữ các nhóm "không thể bị bắt kịp" riêng biệt.

Daily Temperatures (739) là bài khởi động monotone stack chính tắc. Bạn duy trì một stack giảm dần về nhiệt độ và pop khi tìm thấy ngày ấm hơn. Ý tưởng cấu trúc giống nhau: duy trì một sequence với tính chất monotone, cập nhật khi scan. Sự khác biệt là 739 pop các phần tử (mỗi phần tử thoát khi bị dominate), trong khi Car Fleet chỉ push (mỗi fleet leader ở lại).

Largest Rectangle in Histogram (84) khó hơn nhưng cùng họ. Stack duy trì các chỉ số của bars theo chiều cao tăng dần. Mỗi bar được push khi nó kéo dài chuỗi hiện tại, pop khi một bar ngắn hơn kết thúc nó. Lại là stack duy trì tính chất monotone qua linear scan.

Trapping Rain Water (42) dùng ý tưởng tương tự: xử lý từ boundaries vào trong, theo dõi maximum đã thấy như constraint quyết định lượng nước bất kỳ vị trí nào có thể giữ. Logic "constraint từ phần tử dẫn đầu" có cấu trúc giống Car Fleet.

Online Stock Span (901) có lẽ là người anh em gần nhất. Bạn có chuỗi giá, và cho mỗi ngày bạn muốn biết bao nhiêu ngày liên tiếp (kể cả hôm nay) giá không lớn hơn. Stack lưu các span của các ngày bị dominate — giống như Car Fleet lưu các xe bị hấp thụ. Đáng làm tiếp theo nếu bài này cảm thấy tự nhiên.