拼车

记住两步:① 每个行程在两端打 +/- 标记 ② 前缀和还原每站人数。下面每帧都在套这套。

先开一个长度覆盖所有站点的数组 diff,全部填 0。下标就是站点号,值表示「在这一站人数的变化量」。

行程 1([2,1,5]):2 人在站点 1 上车,就在 diff[1] 加上 2(紫色)。

同一行程的 2 人在站点 5 下车,就在 diff[5] 减去 2(红色)。注意只动两端,中间各站不用碰。

行程 2([3,3,7]):3 人在站点 3 上车,就在 diff[3] 加上 3(紫色)。

同一行程的 3 人在站点 7 下车,就在 diff[7] 减去 3(红色)。注意只动两端,中间各站不用碰。

两个行程都打完标记,diff 现在记录了「每站相对上一站的人数变化」。接下来从左往右累加(前缀和),就能还原每一站车上的真实人数。

扫到站点 0:本站净变化 diff[0] = 0。底色框出已累加过的前缀区间。准备把它加进 cur。

结算后站点 0 车上 0 人,0 ≤ 4,这一站没问题,继续往后扫。

扫到站点 1:本站净变化 diff[1] = 2。底色框出已累加过的前缀区间。准备把它加进 cur。

结算后站点 1 车上 2 人,2 ≤ 4,这一站没问题,继续往后扫。

扫到站点 2:本站净变化 diff[2] = 0。底色框出已累加过的前缀区间。准备把它加进 cur。

结算后站点 2 车上 2 人,2 ≤ 4,这一站没问题,继续往后扫。

扫到站点 3:本站净变化 diff[3] = 3。底色框出已累加过的前缀区间。准备把它加进 cur。

结算后站点 3 车上 5 人,5 > 4!此刻车坐不下,代码会在这一站直接返回 false。

扫到站点 4:本站净变化 diff[4] = 0。底色框出已累加过的前缀区间。准备把它加进 cur。

站点 4 车上 5 人,仍 > 容量 4。答案早在站点 3 就定为 false,这里只是把全程人数画完。

扫到站点 5:本站净变化 diff[5] = -2。底色框出已累加过的前缀区间。准备把它加进 cur。

站点 5 车上 3 人,此时已 ≤ 容量 4。答案早在站点 3 就定为 false,这里只是把全程人数画完。

扫到站点 6:本站净变化 diff[6] = 0。底色框出已累加过的前缀区间。准备把它加进 cur。

站点 6 车上 3 人,此时已 ≤ 容量 4。答案早在站点 3 就定为 false,这里只是把全程人数画完。

扫到站点 7:本站净变化 diff[7] = -3。底色框出已累加过的前缀区间。准备把它加进 cur。

站点 7 车上 0 人,此时已 ≤ 容量 4。答案早在站点 3 就定为 false,这里只是把全程人数画完。

扫到站点 8:本站净变化 diff[8] = 0。底色框出已累加过的前缀区间。准备把它加进 cur。

站点 8 车上 0 人,此时已 ≤ 容量 4。答案早在站点 3 就定为 false,这里只是把全程人数画完。

扫描全程,车上人数首次在站点 3 超过容量 4(红色),代码到这一站就返回了;全程峰值 5,所以无法完成所有行程,答案 false。

边界:空行程恒 true、等于容量算通过、重叠峰值超容量则 false。

两个高频追问:差分的提速原理,以及坐标极大时改用排序扫描线。