现在的网站开发都用什么开发,品牌加盟,公司建站系统,软件开发者路线图【LetMeFly】1094.拼车#xff1a;优先队列
力扣题目链接#xff1a;https://leetcode.cn/problems/car-pooling/
车上最初有 capacity 个空座位。车 只能 向一个方向行驶#xff08;也就是说#xff0c;不允许掉头或改变方向#xff09;
给定整数 capacity 和一个数组…【LetMeFly】1094.拼车优先队列
力扣题目链接https://leetcode.cn/problems/car-pooling/
车上最初有 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示例 2
输入trips [[2,1,5],[3,3,7]], capacity 5
输出true提示
1 trips.length 1000trips[i].length 31 numPassengersi 1000 fromi toi 10001 capacity 105
方法一优先队列
首先二话不说对trips按“上车地点”为依据从小到大排个序。
接着创建一个优先队列用于存放“已上车的人”。优先队列的排序依据是“先下车的人优先”。
使用一个变量记录当前车上的人数遍历trips数组 让优先队列中不晚于此位置的人下车 让这批人上车。 期间若出现超载的情况则返回false否则返回true。
时间复杂度 O ( n log n ) O(n\log n) O(nlogn)其中 n l e n ( t r i p s ) nlen(trips) nlen(trips)空间复杂度 O ( n ) O(n) O(n)
AC代码
C
class Solution {
public:bool carPooling(vectorvectorint trips, int capacity) {sort(trips.begin(), trips.end(), [](const vectorint a, const vectorint b) {return a[1] b[1];});int nowPeopleCnt 0;auto cmp [](const pairint, int a, const pairint, int b) {return a.second b.second;};priority_queuepairint, int, vectorpairint, int, decltype(cmp) nowPeople(cmp);for (vectorint trip : trips) {int num trip[0], from trip[1], to trip[2];while (nowPeople.size() nowPeople.top().second from) {nowPeopleCnt - nowPeople.top().first;nowPeople.pop();}nowPeopleCnt num;if (nowPeopleCnt capacity) {return false;}nowPeople.push({num, to});}return true;}
};Python
# from typing import List
# import heapqclass Solution:def carPooling(self, trips: List[List[int]], capacity: int) - bool:trips.sort(keylambda x: x[1])nowPeopleCnt 0nowPeople []for num, from_, to in trips:while nowPeople and nowPeople[0][0] from_:nowPeopleCnt - nowPeople[0][1]heapq.heappop(nowPeople)nowPeopleCnt numif nowPeopleCnt capacity:return Falseheapq.heappush(nowPeople, (to, num))return True同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/134751973
