1. 題目

N 輛車沿著一條車道駛向位于 target 英里之外的共同目的地。

每輛車 i 以恒定的速度 speed[i] （英里/小時），從初始位置 position[i] （英里） 沿車道駛向目的地。

一輛車永遠不會超過前面的另一輛車，但它可以追上去，并與前車以相同的速度緊接著行駛。

此時，我們會忽略這兩輛車之間的距離，也就是說，它們被假定處于相同的位置。

車隊 是一些由行駛在相同位置、具有相同速度的車組成的非空集合。
注意，一輛車也可以是一個車隊。

即便一輛車在目的地才趕上了一個車隊，它們仍然會被視作是同一個車隊。

會有多少車隊到達目的地?

示例： 輸入：target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3] 輸出：3 解釋： 從 10 和 8 開始的車會組成一個車隊，它們在 12 處相遇。 從 0 處開始的車無法追上其它車，所以它自己就是一個車隊。 從 5 和 3 開始的車會組成一個車隊，它們在 6 處相遇。 請注意，在到達目的地之前沒有其它車會遇到這些車隊，所以答案是 3。提示： 0 <= N <= 10 ^ 4 0 < target <= 10 ^ 6 0 < speed[i] <= 10 ^ 6 0 <= position[i] < target 所有車的初始位置各不相同。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/car-fleet
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：
LeetCode 5692. 車隊 II（單調棧）

• 排序后，距離終點近的先處理
• 后車追不上前車，車隊數量+1，更新后面所有車子到達終點需要的最長的時間

class Solution { public:int carFleet(int target, vector<int>& position, vector<int>& speed) {if(position.empty()) return 0;int i, n = position.size();vector<vector<int>> car(n,vector<int>(2));for(i= 0; i < n; i++){car[i][0] = target-position[i];car[i][1] = speed[i];}sort(car.begin(), car.end(), [&](auto a, auto b){return a[0] < b[0];//距離近的先處理});int block = 1;//車隊數量double maxtime, time;maxtime = car[0][0]/double(car[0][1]);//距離近的車按自己速度到達終點的時間for(i = 1; i < n; ++i){time = car[i][0]/double(car[i][1]);//距離遠的車的時間if(maxtime < time)//距離遠的車追不上前車{block++;//車隊+1maxtime = time;//后續車輛最少要花當前車子的時間，才能到達}}return block;} };

968 ms 100.5 MB

總結

以上是生活随笔為你收集整理的LeetCode 853. 车队（排序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。