1094. 拼车(差分堆排序)

本文主要是介绍1094. 拼车(差分堆排序)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: 1094. 拼车

题目

车上最初有 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 ： 使用差分数组 ,对区间 [$fro{m}_i$ ,$t{o}_i$] 同时加$nu{m}_i$。注意在 $t{o}_i$时是立即下车

Review 差分数组

定义

对于一个给定的数组 arr[0…n-1]，其差分数组 diff[0…n-1] 定义如下：

$$diff[0]=arr[0]$$
$$diff[i]=arr[i]-arr[i-1]$$
对于所有 $0<i<n$
这意味着 $ diff[i] $存储了$ arr[i]$和 $arr[i-1] $之间的差值 。

区间加法减法

差分数组的主要用途之一是进行区间加法操作。假设你想对原数组 arr 的子区间 [L, R] 中的所有元素增加一个值 val。使用差分数组，你可以非常高效地完成这个操作：

更新差分数组：

diff[L] += val
如果 R + 1 < n，则 diff[R + 1] -= val.

为啥这样更新

例子 ：

回归到题目 ，我们对 每个 trips的 [$fro{m}_i$ ,$t{o}_i$] 同时加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 ; }
};

这篇关于1094. 拼车(差分堆排序)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---