确定特定行程是否有可用座位

Question

所以我这里有一个有趣的问题，我想找到一个优雅的解决方案。在这种情况下，我实际上没有编写任何代码，因为我正在寻找更多的算法。一旦我知道如何做，我应该能够翻译成一种编程语言。所以这是交易：

假设您有一辆 3 个座位的火车，开往 6 个车站（此处的数字可能有所不同，但如果它适用于这些数字，那么它应该适用于所有车站，我认为拥有实际数字有助于更好地理解问题).

所以我们有1、2、3号座位以及A、B、C、D、E、F站

一个人可以在任何车站进站，前往更远的车站。这里没有环路，所以你不能旅行 F ---> A （这也意味着没有人会进入 F 站）。

另外，我不确定如何表达这一点，但可以这么说，座位不是“分配”的。基本上，如果一个人想去 A-->C 并且座位 1 可用 A-->B 并且座位 2 可用 B-->C 那么我们认为确实有空间供该人乘坐（基本上一个人只会走进去并坐在任何可用的座位上）。

所以现在，我的问题是我想知道在任何时候给定的行程有多少个座位。

正如你所见，如果我有三个人去 A-->F 那么我已经满了，没有人可以进去。

但是，如果我有

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

如果我想去 C-->D，那么我有 2 个可用座位，如果我想去 B-->D，则有 1 个可用座位，依此类推。正如你所知，事情变得非常复杂非常快，所以我需要一种算法来有效地让我计算这个。

现在，我能找到的唯一解决方案是这个（伪代码）：

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);

Answer 1

“我的问题是，我想知道在任何时间给定行程有多少座位可用。”，因为您的火车只是一种方式，我认为时间对您的问题没有任何重要性，如果您是使用某种类型的面向对象编程，您可以添加一个变量空集，它是一个简单的整数，如果有人上火车，它会增加 1，其他则减少 1，以了解给定车站 A 的空座位数你可以做 number_of_empty_seats=total_number_of_seats-(number_of_itinerary_that_end_by_A + number_of_itinerary_that_end_BEFOR_A).