1094. Car Pooling

题目信息

题号:

1094

难度:

Medium

主题:

区间乘客、车辆容量、顺向行驶

原题:

LeetCode 1094

重点:

每个行程在 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。