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

本文概述

• C ++
• Python3

给定到达火车站的所有火车的到达和离开时间, 请找到火车站所需的最少月台数目, 以确保没有火车在等待。我们获得了两个数组, 分别代表了停靠的火车的到达和离开时间。

例子：

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)

我们已经在下面的文章中讨论了其基于排序的简单解决方案。

火车站/汽车站所需的最少月台数量.

在这篇文章中，我们将在multimap中插入所有到达和离开的时间。multimap中元素的第一个值告诉到达/离开的时间，第二个值告诉它是到达还是离开，分别用' a '或' d '表示。

如果它的到达将增加1，否则将减少1。如果我们从STDIN获取输入，那么我们可以直接multimap中插入时间，而不需要在数组中存储时间。

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

方法2：如果所有的到达和离开发生在同一天, 那么我们可以使用辅助数组来计算O(n)中所需的月台数量。

每当发生到达时, 我们都会增加所需月台的数量, 而当发生偏离时, 我们会在该时间点减少所需月台的数量, 此后, 我们将获得累计总和, 这将提供所有时间点所需的月台数量, 这些值中的最大值是我们的答案。

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

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。