1094. Car Pooling¶
题目信息¶
- 题号:
1094
- 难度:
Medium
- 主题:
区间乘客、车辆容量、顺向行驶
- 原题:
- 重点:
每个行程在
from上车、到达to时下车,乘客占用区间为[from, to);车辆只能向东且容量任何时刻都不能超限
题目重述¶
车辆有固定座位容量 capacity,只能沿位置编号增大的方向行驶。数组 trips[i] = [numPassengers_i, from_i, to_i] 表示有指定数量的乘客在 from_i 上车,并在 to_i 下车。
判断能否完成全部行程,使任意位置区间内的车上人数都不超过容量。同一位置发生下车和上车时,抵达该位置的乘客先结束占用,因此行程的有效占用范围是左闭右开区间 [from_i, to_i)。
1 <= trips.length <= 1000,每项长度为 3,1 <= numPassengers_i <= 100,0 <= from_i < to_i <= 1000,1 <= capacity <= 10^5。
自建示例¶
同一地点下车后仍可能因新乘客而超载:
输入:trips = [[2,1,5],[3,5,7],[4,3,6]], capacity = 6
输出:false
解释:位置 3 到 5 之间共有 6 人;到达位置 5 时前两人下车、三人上车,而第三段行程的四人仍在车上,人数变为 7,超过容量。
下车后立即使用空出的座位:
输入:trips = [[2,0,2],[3,2,4]], capacity = 3
输出:true
解释:第一批乘客在位置 2 全部下车后,第二批三人才上车,车上人数最多恰好等于容量 3。