无固定分配规则下列车跨行程座位可用数计算算法需求

问题背景 #

现有一列配备3个座位、途经A、B、C、D、E、F共6个站点的列车（座位数与站点数可灵活调整）。乘客仅能从某一站点乘车前往后续站点，无反向行程（即无F→A这类行程，且无人在F站乘车）。座位无固定分配规则：若乘客行程为A→C，当座位1在A→B时段空闲、座位2在B→C时段空闲时，该乘客可分段就座，视为有可用座位。

核心需求 #

设计高效算法，计算任意给定行程（x→y）的可用座位数。

示例说明 #

给定4条预订记录：

A-->C
A-->B
A-->E
B-->D

• C→D行程有1个可用座位
• B→D行程无可用座位

现有伪代码方案 #

itinerary = x-->y

for stations s going from x to y
    seatsAvailable[s] = 3 - count reservations starting at or before x and ending after x

availableSeats = min(seatsAvailable);

该方案的问题在于：每个站点都要遍历所有预订统计符合条件的记录，时间复杂度为O(N*M)（N为目标行程的站点数，M为预订总数），数据量大时效率极低。

更优算法实现思路 #

核心优化方向 #

通过预处理构建差分数组+前缀和，结合区间最大值查询结构，将查询复杂度降至O(1)或O(logN)，预处理复杂度仅为O(M+N)。

步骤1：构建站点载客变化差分数组

1. 先将所有站点按顺序编号（例如A=0、B=1、C=2、D=3、E=4、F=5）。
2. 创建长度等于站点数的差分数组diff，初始值全为0。
3. 遍历每条预订记录start→end：
   • diff[start] += 1（表示对应站点上车1人）
   • diff[end] -= 1（表示对应站点下车1人）

步骤2：计算各路段的实时载客量

基于差分数组计算前缀和数组load，其中load[s]代表列车在s→s+1路段的载客人数。

步骤3：快速查询目标行程的可用座位

1. 提前用ST表（稀疏表）或线段树对load数组构建区间最大值查询结构。
2. 对于给定行程x→y，我们需要查询x到y-1区间内的最大载客量max_load（因为目标行程覆盖x→x+1到y-1→y的所有路段）。
3. 可用座位数 = 总座位数 - max_load

复杂度对比 #

• 预处理阶段：O(M + N)（M为预订总数，N为站点数）
• 查询阶段：O(1)（ST表实现）或O(logN)（线段树实现），远优于原方案的O(N*M)

示例验证 #

针对给出的预订记录：

1. 构建差分数组后得到：diff = [3, 0, -1, -1, -1, 0]
2. 计算前缀和load数组：load = [3, 3, 2, 1, 0]（分别对应A→B、B→C、C→D、D→E、E→F路段的载客量）
3. 查询C→D（x=2,y=3）：区间为[2,2]，max_load=2，可用座位=3-2=1，符合示例结果。
4. 查询B→D（x=1,y=3）：区间为[1,2]，max_load=3，可用座位=3-3=0，符合示例结果。

内容的提问来源于stack exchange，提问作者Osuwariboy