一个火车站所需的最少站台数量 [英] Minimum number of platforms required for a railway station
问题描述
问题如下:给定到达火车站的所有火车的到达和离开时间，任务是找到火车站所需的最少站台数量，以便没有火车等待.火车可以在午夜之前到达，午夜之后到达"
我了解传统问题如何在没有火车可以在午夜之前到达并在午夜之后离开的条件下工作，因为我见过的许多解决方案都没有考虑午夜条件.
我的方法是只使用传统的蛮力"然而，我考虑了午夜前到达并在午夜后离开的特殊情况，称为交叉".我已经编写了以下代码(在 Python 中)，但我不完全确定这是否是正确的方法.对于选定的输入，代码可以正常工作，但是有没有更好/更清晰的方法来解决这个问题而不使用蛮力?
def findPlatform(arr, dep, n):# 交叉意味着火车在午夜前到达并在午夜后离开我 = 0平台最大值 = 1当我 <ñ:平台 = 1j = i+1当 j <ñ:# 交叉如果 arr[i] >深度[i]:# 交叉if ((arr[i] <= arr[j] and arr[i] >= dep[j]) or (arr[j] <= arr[i] and arr[j] >= dep[一世])):如果 arr[j] >深度[i]:平台 += 1# 不交叉别的:if ((arr[i] <= arr[j] and arr[i] >= dep[j]) or (arr[j] <= arr[i] and arr[j] >= dep[一世])):平台 += 1# 不交叉别的:# 交叉如果 arr[j] >深度[j]:if ((arr[i] >= arr[j] and arr[i] >= dep[j]) or (arr[j] >= arr[i] and arr[j] <= dep[一世])):平台 += 1# 不交叉别的:如果 ((arr[i] >= arr[j] and arr[i] <= dep[j]) 或 (arr[j] >= arr[i] and arr[j] <= dep[一世])):平台 += 1j += 1如果平台>最大平台:platmax = 平台我 += 1返回平台#驱动代码#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]深度 = [300, 400, 450, 500, 530, 540, 1150, 1155, 10, 100, 110, 250]n = len(arr)打印(所需的最小平台数="，findPlatform(arr, dep, n))这个问题让我想起了经典的一辆公共汽车上有 10 个乘客.第一站3人下车2人上车.第二站4人下车1人上车.第三站1人下车5人上车.车上有多少人?>
这个问题真的很容易回答，因为你可以只统计公交车上的乘客人数，然后遍历事件并调整人数.
在您的问题中，不是公交车上的乘客，而是车站中的火车.但这不会改变任何事情.我们可以在 24 小时内迭代事件(火车到达、火车出发)，记录车站中的火车数量，每次到达时调整 +1，每次出发时调整 -1.我们还需要计算列车的最大数量.
我们在公共汽车上的乘客"中获得的一个信息故事是公交车上最初的乘客人数.在您的问题中，这转化为在 24 小时时段开始时车站内有多少列火车"，即有多少列火车在午夜前到达但在午夜后离开.这些正是到达时间较晚"的火车.比他们的离开.所以我们可以做一个简单的函数来计算这些火车:
def get_nb_train_at_midnight(arr, dep):返回 sum(1 for (a,d) in zip(arr,dep) 如果 a > d)然后我们需要按顺序遍历事件列表，所以让我们构建该列表.一个事件是一对 (time, type)，其中 type 是 'arr' 或 'dep'.如果我们还想跟踪当前在车站的火车，我们可以将其设为三元组 (time, type, id)；但是我们只关心火车的数量，所以我们可以忘记他们的id.让我们创建一个函数来构建事件列表:
def get_list_of_events(arr, dep):事件 = [(t, 'arr') for t in arr] + [(t, 'dep') for t in dep]事件排序()返回事件注意:我们可以使用 key 可选参数进行排序来指定我们要按时间排序，但时间已经是该对中的第一个元素，因此这是自动的.另外，如果我们想用火车的 id 制作三元组，我们可以写 [(t, 'arr', i) for (i, t) in enumerate(arr)] 来得到身份证.
所以现在我们有了按顺序排列的事件列表和初始列车数量，因此我们可以遍历事件列表并跟踪车站中的列车数量:
def get_max_nb_trains(events, nb_trains_at_midnight):nb_trains = nb_trains_at_midnightmax_trains = nb_trains事件中的(时间，类型):nb_trains += (1 if type == 'arr' else -1)max_trains = max(max_trains, nb_trains)返回 max_trains让我们在 python repl 中尝试这些函数:
<预><代码>>>>arr = [1,3,7,9,10,10,19,23]>>>深度 = [11,4,11,10,11,2,2,2]>>>事件 = get_list_of_events(arr, dep)>>>nb_trains_midnight = get_nb_train_at_midnight(arr, dep)>>>事件[(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_midnight3>>>get_max_nb_trains(事件，get_nb_train_at_midnight(arr，dep))5在此示例中，您可以看到我确实在事件列表中包含了火车的 ID，尽管该信息没有用.
The problem is as follows: "Given arrival and departure times of all trains that reach a railway station, the task is to find the minimum number of platforms required for the railway station so that no train waits. Trains can arrive before midnight and arrive after midnight"
I understand how the traditional problem works without the condition that trains can arrive before midnight and leave after midnight, as many of the solutions I've seen for this problem doesn't take the midnight condition into account.
My approach was to just use the traditional "Brute Force" method however I considered the trains which arrived before midnight and left after midnight special cases called "Crossover". I've written the following code (in Python), but I'm not entirely certain whether it is the correct approach. For the selected input the code works correctly, but is there any better/more clearer way to approach this problem without using Brute Force?
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))
This problem reminds me of the classic '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?'
This problem is really easy to answer, because you can just keep a count of the number of passengers in the bus, and iterate through the events and adjust the count.
In your problem, instead of passengers in a bus, it's trains in a station. But that doesn't change anything. We can iterate through the events during a 24h period (train arrival, train departure), keep a count of the number of trains in the station, adjust it by +1 at every arrival and -1 at every departure. We also need to keep count of the max number of trains.
One information that we had in the "passengers in a bus" story was the initial number of passengers in the bus. In your problem this translates to "how many trains are in the station at the start of the 24h period", i.e., how many trains arrive before midnight but leave after midnight. Those are exactly the trains whose arrival is "later" than their departure. So we can make a simple function to count these trains:
def get_nb_train_at_midnight(arr, dep):
return sum(1 for (a,d) in zip(arr,dep) if a > d)
Then we need to iterate through the list of events in order, so let's build that list. An event is a pair (time, type) where type is either 'arr' or 'dep'. We could have made it a triplet (time, type, id) if we also wanted to keep track of which train was currently in the station; but we only care about the number of trains, so we can forget about their id. Let's make a function to build the list of events:
def get_list_of_events(arr, dep):
events = [(t, 'arr') for t in arr] + [(t, 'dep') for t in dep]
events.sort()
return events
Note: we could use the key optional argument to sort to specify we want to sort by time, but time is already the first element in the pair so that's automatic. Also, if we wanted to make triplets with the id of the train, we could write [(t, 'arr', i) for (i, t) in enumerate(arr)] to get the id.
So now we have the list of events in order, and the initial number of trains, so we can iterate through the list of events and keep track of the number of trains in station:
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
Let's try those functions in a 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
In this example you can see I did include the ids of the trains in the event list, although that information is not useful.
这篇关于一个火车站所需的最少站台数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
