853. Car Fleet

Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:

https://leetcode.com/problems/car-fleet/description/

Table of Contents

1. Cách tiếp cận vấn đề

Bài toán cho n chiếc xe với các vị trí xuất phát khác nhau bắt đầu từ vị trí 0 đến vị trí mục tiêu.

Cho 2 mảng position và speed có cùng chiều dài n, với mỗi position[i] đại diện cho vị trí bắt đầu của chiếc xe thứ i và speed[i] đại diện cho tốc độ của chiếc xe thứ i với đơn vị là miles per hour (Mph).

1 chiếc xe không thể vượt qua chiếc xe khác, nhưng nó có thể đi song song với chiếc xe đó với tốc độ của chiếc xe thấp hơn.

1 nhóm xe - Car Fleet được định nghĩa là 1 hoặc nhiều chiếc xe đi song song với nhau, vận tốc trong 1 nhóm xe là vận tốc nhỏ nhất trong nhóm. Nếu những chiếc xe gặp nhau ở đích đến cùng 1 thời điểm, thì cũng được tính là 1 nhóm xe.

Và bài toán yêu cầu ta tính toán xem có bao nhiêu nhóm xe được thành lập khi tất cả các xe về đích tại vị trí mục tiêu. Trong ví dụ trên, ta thấy có 4 nhóm xe riêng biệt được thành lập từ 8 chiếc xe, 4 nhóm xe này sẽ được giữ nguyên khi về tới điểm đích nên đáp án sẽ là 4.

Bài toán đã cho chúng ta vị trí bắt đầu, vận tốc và vị trí kết thúc, từ đó ta có thể dễ dàng tính ra được quãng đường = target - position[i] và thời gian = quãng đường / vận tốc. Từ yếu tố thời gian, ta sẽ biết được có bao nhiêu nhóm xe được hình thành. Hãy cùng tìm hiểu thông qua ví dụ sau:

• Input: target = 12, position = [10,8,0,5,3], speed = [2,4,2,1,3].
• Output: 2

Điểm mấu chốt để giải bài toán này là ta sẽ hoàn toàn dựa vào yếu tố thời gian, không cần quan tâm 2 xe/nhóm xe gặp nhau tại vị trí nào cả, ta chỉ cần biết nếu gặp nhau thì nhóm xe đó sẽ di chuyển về đích với thời gian của xe có vận tốc nhỏ nhất (thời gian sẽ tỷ lệ nghịch nên là lớn nhất). Và sẽ có 2 hướng tiếp cận chính:

• Tiếp cận xuôi: Duyệt thời gian của vị trí đầu đến cuối.
• Tiếp cận ngược: Duyệt thời gian của vị trí cuối về đầu.

Theo cách tiếp cận xuôi, với mỗi thời gian được duyệt:

• Nếu thời gian đó nhanh hơn thời gian của nhóm trước đó thì không sao, nó sẽ tách ra làm 2 nhóm riêng biệt.
• Tuy nhiên khi gặp 1 thời gian chậm hơn thời gian của nhóm trước, lúc này ta sẽ gộp xe hiện tại vào nhóm trước đó và:
• Thời gian của nhóm hiện tại sẽ là thời gian của xe đi chậm hơn.
• Ta cần phải duyệt lại tất cả các nhóm trước, để xem nhóm hiện tại có bị các nhóm trước đó vượt qua không.
• Ví dụ như trong hình ở trên
• Xe thứ hai có thời gian về đích là 3h tưởng là đã tách nhóm với xe đầu tiên về đích sau 6h
• Tuy nhiên sau khi duyệt đến xe thứ ba với thời gian về đích là 7h, nó sẽ bị xe thứ hai bắt kịp tại 1 thời điểm nào đó (không cần quan tâm) và sẽ di chuyển cùng nhau với thời gian là 7h.
• Lúc này ta đang có 2 nhóm xe, 1 nhóm về đích trong thời gian 6h, nhóm còn lại ở sau về đích trong thời gian 7h -> Cần gộp lại 1 lần nữa thành chung 1 nhóm có thời gian 7h.

Như vậy ta cần sử dụng cấu trúc dữ liệu Monotonic Stack để lưu trữ thời gian, và thời gian phải được duy trì theo thứ tự giảm dần, mỗi thời gian như vậy chính là đại diện cho thời gian của từng nhóm -> đáp án của bài toán chính là kích thước của Monotonic Stack.

Mỗi lần ta gặp một thời gian x:

• Ta sẽ kiểm tra giá trị top của Stack và sẽ pop ra các phần tử trong Stack cho đến khi top > x (đảm bảo tính giảm dần) hoặc stack empty thì dừng lại.
• Hay nói cách khác, ta sẽ tìm và gộp thời gian của các nhóm trước đó có thời gian <= x (đi nhanh hơn hoặc bằng x) bằng chính giá trị x và tiếp tục bỏ vào stack để làm đại diện cho nhóm đó.

Về độ phức tạp về mặt thời gian thì nó sẽ là O(n) (mặc dù có bước pop và push stack nhưng nó vẫn đảm bảo mỗi phần tử chỉ được pop hoặc push đúng 1 lần). Tuy nhiên cách làm này còn hơi rườm rà và tốn thêm bộ nhớ Stack nên trong phạm vị bài viết lần này mình sẽ tập trung chủ yếu vào cách làm ngược.

2. Solution & Phân Tích

Vì các nhóm xe chắc chắn phải có thời gian về đích khác nhau và giảm dần, nên ta sẽ tư duy ngược và thay đổi góc nhìn vấn đề: thay vì duyệt từ đầu đến cuối và phải bận tâm về việc phải duy trì Monotonic Stack, thì ta có thể duyệt theo chiều ngược lại và không cần sử dụng đến Stack.

Cụ thể sau khi tính được thời gian hoàn thành tại mỗi vị trí, ta sẽ dùng 1 biến để lưu trữ giá trị max - đại diện cho thời gian của nhóm hiện tại và 1 biến đếm để đếm số lượng nhóm xe. Thay vì phải sắp xếp mảng position theo thứ tự giảm dần, ta chỉ cần duyệt tất cả vị trí từ cuối cùng (target) đến vị trí 0, với mỗi vị trí:

• Ta cần đảm bảo vị trí đó là hợp lệ (có xuất hiện trong mảng position và đã được tính thời gian hoàn thành). 
• Ta sẽ so sánh nó với giá trị max hiện tại - giá trị thời gian của nhóm xe hiện tại:
• Nếu tìm được thời gian lớn hơn giá trị max - hay phát hiện ra một nhóm có thời gian chậm hơn nhóm hiện tại, ta sẽ cập nhật lại giá trị max và tăng biến đếm kết quả lên 1.
• Ngược lại nếu phần tử thời gian hiện tại nhỏ hơn hoặc bằng max, điều này chứng tỏ là chúng đang chúng 1 nhóm xe với thời gian chính là giá trị max hiện tại, ta không cần làm gì trong trường hợp này.
• Đáp án của bài toán chính là gía trị của biến đếm.

Tại sao ta lại có thể áp dụng được cách làm này? Lý do là vì tính chất quan trọng được suy ra từ đề bài:

Mỗi khi 1 chiếc xe có thời gian hoàn thành ngắn hơn gặp 1 xe có thời gian hoàn thành lâu hơn, nó sẽ xát nhập vào thành 1 nhóm xe và di chuyển về đích với thời gian hoàn thành của nhóm xe đó.

-> Điều này có nghĩa là ta chỉ cần quan tâm vào những chiếc xe nào mà có thời gian hoàn thành lâu nhất tính từ vạch đích trở về xuất phát. Và nó sẽ đại diện cho tất cả các xe đi nhanh hơn ở trước nó, cho đến khi ta tìm được 1 chiếc xe nào có thời gian hoàn thành lớn hơn nó để tạo ra 1 nhóm xe khác.

Như trong ví dụ này sẽ có 3 nhóm xe, ta chỉ cần quan tâm 2 giá trị thời gian là: 7,1 mà không cần quan tâm các giá trị khác.

• Nhóm thứ nhất: Xe thứ năm có thời gian về đích là 1h, xe thứ tư cùng có thời gian là 1h nên xếp ở chung nhóm.
• Nhóm thứ hai: Xe thứ ba có thời gian về đích là 7h, lúc này chậm hơn nhóm thứ nhất nên nó chính là cột mốc để tạo nhóm xe thứ hai. Xe thứ hai có thời gian về đích là 4h nhưng lại đứng trước xe thứ ba nên phải gộp chung lại thành một nhóm với nó, tương tự như xe đầu tiên với thời gian là 6h sẽ bị gộp lại chung nhóm và di chuyển với thời gian là 7h.
• Ta chỉ cần so sánh thời gian với giá trị đại diện cho nhóm xe trước đó mà mà thôi, nên đó là lý do vì sao dùng giá trị max để so sánh.

Time-Complexity: O(n)

Space-Complexity: O(n)

3. Code

Điểm chung của 2 đoạn code ở dưới là ta sẽ dùng 1 mảng times để đại diện cho tất cả các vị trí từ 0 đến target. Đối với những vị trí hợp lệ thì sẽ có giá trị thời gian tương ứng trong mảng times.

3.1. Tư duy xuôi

3.2. Tư duy ngược

© hieulm2k | Buy me a coffee