# 火车站/汽车站所需的最少月台数量|S2（基于Map的方法）

2021年3月26日17:48:02 发表评论 364 次浏览

## 本文概述

``````Input:  arr[]  = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
dep[]  = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}
Output: 3
There are at-most three trains at a time
(time between 11:00 to 11:20)``````

``````// Program to find minimum number of platforms
// required on a railway station
#include <bits/stdc++.h>
using namespace std;

int findPlatform( int arr[], int dep[], int n)
{
// Insert all the times (arr. and dep.)
// in the multimap.
multimap< int , char > order;
for ( int i = 0; i < n; i++) {

// If its arrival then second value
// of pair is 'a' else 'd'
order.insert(make_pair(arr[i], 'a' ));
order.insert(make_pair(dep[i], 'd' ));
}

int result = 0;
int plat_needed = 0;

multimap< int , char >::iterator it = order.begin();

// Start iterating the multimap.
for (; it != order.end(); it++) {

// If its 'a' then add 1 to plat_needed
// else minus 1 from plat_needed.
if ((*it).second == 'a' )
plat_needed++;
else
plat_needed--;

if (plat_needed > result)
result = plat_needed;
}
return result;
}

// Driver code
int main()
{
int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << "Minimum Number of Platforms Required = "
<< findPlatform(arr, dep, n);
return 0;
}``````

``Minimum Number of Platforms Required = 3``

## C ++

``````// Program to find minimum number of platforms
// required on a railway station
#include <bits/stdc++.h>
using namespace std;

int minPlatform( int arrival[], int departure[], int n)
{

// as time range from 0 to 2359 in 24 hour clock, // we declare an array for values from 0 to 2360
int platform[2361] = {0};
int requiredPlatform = 1;
for ( int i = 0; i < n; i++) {

// increment the platforms for arrival
++platform[arrival[i]];

// once train departs we decrease the platform count
--platform[departure[i] + 1];
}

// We are running loop till 2361 because maximum time value
// in a day can be 23:60
for ( int i = 1; i < 2361; i++) {

// taking cumulative sum of platform give us required
// number of platform fro every minute
platform[i] = platform[i] + platform[i - 1];
requiredPlatform = max(requiredPlatform, platform[i]);
}
return requiredPlatform;
}

// Driver code
int main()
{
int arr[] = { 900, 940, 950, 1100, 1500, 1800 };
int dep[] = { 910, 1200, 1120, 1130, 1900, 2000 };
int n = sizeof (arr) / sizeof (arr[0]);
cout << "Minimum Number of Platforms Required = "
<< minPlatform(arr, dep, n);
return 0;
}``````

## Python3

``````# Python3 program to find minimum number
# of platforms required on a railway station
def minPlatform(arrival, departure, n):

# As time range from 0 to 2359 in
# 24 hour clock, we declare an array
# for values from 0 to 2360
platform = [ 0 ] * 2631
requiredPlatform = 1

for i in range (n):

# Increment the platforms for arrival
platform[arrival[i]] + = 1

# Once train departs we decrease the
# platform count
platform[departure[i] + 1 ] - = 1

# We are running loop till 2361 because
# maximum time value in a day can be 23:60
for i in range ( 1 , 2631 ):

# Taking cumulative sum of
# platform give us required
# number of platform fro every minute
platform[i] = platform[i] + platform[i - 1 ]
requiredPlatform = max (requiredPlatform, platform[i])

return requiredPlatform

# Driver code
arr = [ 900 , 940 , 950 , 1100 , 1500 , 1800 ]
dep = [ 910 , 1200 , 1120 , 1130 , 1900 , 2000 ]
n = len (arr)

print ( "Minimum Number of Platforms Required = " , minPlatform(arr, dep, n))

# This code is contributed by PawanJain1``````

``Minimum Number of Platforms Required = 3``