Problem: 1094. 拼车
文章目录
- 题目
- 思路
- Review 差分数组
- 定义
- 区间加法减法
- 更新差分数组：
- 为啥这样更新
- 思路1 Code
- 思路2 Code
题目
车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
示例 1：
输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false
思路
思路1 ： 使用堆排序（优先队列维护）,每到一个上车或者下车的位置 统计一下当前车上的人数，如果大于了
capacity就返回false；思路2 ： 使用差分数组 ,对区间 [
,
] 同时加
。注意在
Review 差分数组
定义
对于一个给定的数组 arr[0…n-1]，其差分数组 diff[0…n-1] 定义如下：
对于所有
这意味着 $ diff[i]
区间加法减法
差分数组的主要用途之一是进行区间加法操作。假设你想对原数组 arr 的子区间 [L, R] 中的所有元素增加一个值 val。使用差分数组，你可以非常高效地完成这个操作：
更新差分数组：
diff[L] += val
如果 R + 1 < n，则 diff[R + 1] -= val.
为啥这样更新
例子 ：
回归到题目 ，我们对 每个 trips的 [ ,
] 同时加Num，统计有没有超过’capacity`。
思路1 Code
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
// 创建一个事件列表
vector<pair<int, int>> events;
for (auto& trip : trips) {
events.push_back({trip[1], trip[0]}); // 上车事件
events.push_back({trip[2], -trip[0]}); // 下车事件
}
// 对事件按地点排序
sort(events.begin(), events.end());
int currentPassengers = 0;
for (auto& event : events) {
currentPassengers += event.second;
if (currentPassengers > capacity) {
return false;
}
}
return true;
}
};思路2 Code
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
int maxx = 0 ;
// 利用差分数组
for(auto & trip: trips ) {
maxx = max(maxx ,trip[2]) ;
}
vector<int> diff(maxx+1) ;
// 对区间[L,R]同时加 val
// 差分数组 diff[L] +val diff[R+1] -val
for(const auto &trip : trips) {
diff[trip[1]] +=trip[0] ;
diff[trip[2]] -=trip[0] ;
}
int count = 0 ;
for(int i = 0 ; i<=maxx ; ++i) {
count+=diff[i] ;
if(count >capacity) {
return false ;
}
}
return true ;
}
};