火车站所需站台最少数量

问题如下： “给定到达火车站的所有火车的到达和出发时间，任务是找到火车站所需的最少站台数量，以便没有火车等待。火车可以在午夜之前到达，也可以在午夜之后到达”

我理解传统问题是如何在没有火车可以在午夜之前到达并在午夜之后离开的条件下工作的，因为我见过的这个问题的许多解决方案都没有考虑午夜条件。

我的方法是只使用传统的“蛮力”方法，但我考虑了午夜之前到达并在午夜之后离开的特殊情况，称为“交叉”。 我已经编写了以下代码（用Python），但我不完全确定这是否是正确的方法。对于选定的输入，代码可以正常工作，但是有没有更好/更清晰的方法来解决这个问题而不使用暴力？

def findPlatform(arr, dep, n):
    # Crossover means a train arrives before midnight and leaves after midnight
    i = 0
    platmax = 1
    while i < n:
        platforms = 1
        j = i+1
        while j < n:
            # Crossover
            if arr[i] > dep[i]:
                # Crossover
                if ((arr[i] <= arr[j] and arr[i] >= dep[j]) or (arr[j] <= arr[i] and arr[j] >= dep[i])):
                    if arr[j] > dep[i]:
                        platforms += 1
                # Not Crossover
                else:
                    if ((arr[i] <= arr[j] and arr[i] >= dep[j]) or (arr[j] <= arr[i] and arr[j] >= dep[i])):
                        platforms += 1
            # Not Crossover
            else:
                # Crossover
                if arr[j] > dep[j]:
                    if ((arr[i] >= arr[j] and arr[i] >= dep[j]) or (arr[j] >= arr[i] and arr[j] <= dep[i])):
                        platforms += 1
                # Not Crossover
                else:
                    if ((arr[i] >= arr[j] and arr[i] <= dep[j]) or (arr[j] >= arr[i] and arr[j] <= dep[i])):
                        platforms += 1
            j += 1
        if platforms > platmax:
            platmax = platforms
                
        i += 1
    return platmax
# driver code
  
#arr = [900, 940, 950, 1100, 1500, 1800];
#dep = [910, 1120, 1130, 1200, 1900, 2000];
arr = [200, 240, 300, 420, 430, 455, 950, 1130, 2300, 2330, 2340, 2350]
dep = [300, 400, 450, 500, 530, 540, 1150, 1155, 10, 100, 110, 250]
n = len(arr) 
  
print("Minimum Number of Platforms Required = ", 
        findPlatform(arr, dep, n))

这个问题让我想起了经典的“一辆公交车上有10名乘客”。在第一站，3名乘客下车，2名乘客上车。在第二站，4名乘客下车，1名乘客上车。在第三站，1名乘客下车，5名乘客上车。车上有多少乘客？

这个问题确实很容易回答，因为您只需统计公交车上的乘客人数，然后迭代事件并调整计数即可。

在你的问题中，不是公共汽车上的乘客，而是车站里的火车。但这并没有改变任何事情。我们可以迭代 24 小时内的事件（火车到达、火车出发），统计车站内的火车数量，每次到达时调整 +1，每次出发时调整 -1。我们还需要计算火车的最大数量。

我们在“公共汽车上的乘客”故事中获得的信息之一是公共汽车上的最初乘客数量。在您的问题中，这意味着“24 小时开始时车站有多少趟火车”，即有多少趟火车在午夜之前到达但在午夜之后离开。这些正是到达时间比出发时间“晚”的火车。所以我们可以创建一个简单的函数来计算这些火车的数量：

def get_nb_train_at_midnight(arr, dep):
   return sum(1 for (a,d) in zip(arr,dep) if a > d)

然后我们需要按顺序迭代事件列表，所以让我们构建该列表。一个事件是一对(time, type) where type或者是'arr' or 'dep'。我们可以把它做成三元组(time, type, id)如果我们还想跟踪当前车站有哪趟火车；但我们只关心火车的数量，所以我们可以忘记它们的 ID。让我们创建一个函数来构建事件列表：

def get_list_of_events(arr, dep):
    events = [(t, 'arr') for t in arr] + [(t, 'dep') for t in dep]
    events.sort()
    return events

注意：我们可以使用 key 可选参数进行排序来指定我们要按时间排序，但时间已经是该对中的第一个元素，因此这是自动的。另外，如果我们想用火车的 id 来生成三元组，我们可以写[(t, 'arr', i) for (i, t) in enumerate(arr)]获取id。

现在我们有了按顺序排列的事件列表和初始列车数量，因此我们可以迭代事件列表并跟踪车站的列车数量：

def get_max_nb_trains(events, nb_trains_at_midnight):
    nb_trains = nb_trains_at_midnight
    max_trains = nb_trains
    for (time, type) in events:
        nb_trains += (1 if type == 'arr' else -1)
        max_trains = max(max_trains, nb_trains)
    return max_trains

让我们在 python repl 中尝试这些函数：

>>> arr = [1,3,7,9,10,10,19,23]
>>> dep = [11,4,11,10,11,2,2,2]
>>> events = get_list_of_events(arr, dep)
>>> nb_trains_midnight = get_nb_train_at_midnight(arr, dep)
>>> events
[(1, 'arr', 0), (2, 'dep', 5), (2, 'dep', 6), (2, 'dep', 7), (3, 'arr', 1), (4, 'dep', 1), (7, 'arr', 2), (9, 'arr', 3), (10, 'arr', 4), (10, 'arr', 5), (10, 'dep', 3), (11, 'dep', 0), (11, 'dep', 2), (11, 'dep', 4), (19, 'arr', 6), (23, 'arr', 7)]
>>> nb_trains_midnight
3
>>> get_max_nb_trains(events, get_nb_train_at_midnight(arr, dep))
5

在此示例中，您可以看到我确实在事件列表中包含了火车的 ID，尽管该信息没有用。