# 1094. Car Pooling

You are driving a vehicle that has `capacity` empty seats initially available for passengers.  The vehicle only drives east (ie. it cannot turn around and drive west.)

Given a list of `trips``trip[i] = [num_passengers, start_location, end_location]` contains information about the `i`-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off.  The locations are given as the number of kilometers due east from your vehicle’s initial location.

Return `true` if and only if it is possible to pick up and drop off all passengers for all the given trips.

Example 1:

``````Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
``````

Example 2:

``````Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
``````

Example 3:

``````Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true
``````

Example 4:

``````Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true
``````

Constraints:

1. `trips.length <= 1000`
2. `trips[i].length == 3`
3. `1 <= trips[i][0] <= 100`
4. `0 <= trips[i][1] < trips[i][2] <= 1000`
5. `1 <= capacity <= 100000`

``````class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
int cur = 0;
vector<vector<int>> data;
for (auto trip : trips) {
data.push_back({trip[1], trip[0]});
data.push_back({trip[2], -trip[0]});
}
sort(data.begin(), data.end());
for (auto &a : data) {
cur += a[1];
if (cur > capacity) return false;
}
return true;
}
};
``````

``````class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
int cur = 0;
vector<int> cnt(1001);
for (auto &trip : trips) {
cnt[trip[1]] += trip[0];
cnt[trip[2]] -= trip[0];
}
for (int i = 1; i <= 1000; ++i) {
cur += cnt[i];
if (cur > capacity) return false;
}
return true;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1094

Meeting Rooms II

https://leetcode.com/problems/car-pooling/

https://leetcode.com/problems/car-pooling/discuss/317610/JavaC%2B%2BPython-Meeting-Rooms-III

https://leetcode.com/problems/car-pooling/discuss/317611/C%2B%2BJava-O(n)-Thousand-and-One-Stops

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation