題目： LeetCode - 1094. Car Pooling

題目說明

給一個陣列 trips 及一個整數 capacity，trips 中每個元素包含三個數，依次代表搭車人數、上車站、下車站，capacity 代表公車能同時容納的最大人數，求公車在運送期間人數是否會超過 capacity。

解題思路

由於題目有說上車站及下車站的值不會超過 1000，所以定義一個陣列表示站，紀錄每個站會變動的人數，先遍歷 trips，將上車站加上上車的人數，下車站減去下車的人數，接著遍歷 timeStamp，紀錄到目前為止車上的人數，若是人數大於 capacity 回傳 false，否則遍歷結束後回傳 true。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity)
    {
        int timeStamp[1001] = {}, curCap{};
        for(const auto& v : trips) timeStamp[v[1]] += v[0], timeStamp[v[2]] -= v[0];
        for(const auto& num : timeStamp)
        {
            curCap += num;
            if(curCap > capacity) return false;
        }
        return true;
    }
};