火车站所需的最少站台数量

Question

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

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

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

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

Answer 1

这个问题让我想起了经典'There are 10 passengers in a bus. At first stop, 3 passengers get off and 2 get in. At second stop, 4 passengers get off and 1 get in. At third stop, 1 passenger get out and 5 get in. How many passengers are in the bus?'

这个问题真的很容易回答，因为你可以只统计公交车上的乘客人数，然后遍历事件并调整计数。

在你的问题中，不是公共汽车上的乘客，而是车站里的火车。但这并没有改变任何东西。我们可以在 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)，其中 type 是 'arr' 或 '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，尽管该信息没有用。

Answer 2

测试这个工作代码

import java.util.Arrays;

public class TrainsDepArr
{
static int minimumNumberOfPlatform(int array[], int departure[], int n) 
{ 
    Arrays.sort(array); 
    Arrays.sort(departure); 
        
    int plat_needed = 1, maxPlatform = 1; 
        int i = 1, j = 0; 
    
        while (i < n && j < n) { 
        
            if (array[i] <= departure[j]) 
            { 
                plat_needed++; 
            i++; 
                if (plat_needed > maxPlatform) 
            maxPlatform = plat_needed;
            } 
       else if (array[i] > departure[j]) { 
                plat_needed--; 
                j++; 
            } 
             
    } 

        return maxPlatform; 
    } 
    public static void main(String[] args)
{
   int[] arrival = { 100, 140, 150, 200, 215, 400 };
        int[] departure = {110, 300, 220, 230, 315, 600};
         int n = arrival.length; 

    System.out.print("Minimum platforms required is "
                    + minimumNumberOfPlatform(arrival, departure,n));
}
}

火车站所需的最少站台数量

Minimum number of platforms required for a railway station

python

algorithm

greedy