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

本文概述

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)

我们已经在下面的文章中讨论了其基于排序的简单解决方案。
火车站/汽车站所需的最少月台数量.
【火车站/汽车站所需的最少月台数量|S2（基于Map的方法）】在这篇文章中，我们将在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 = 1for 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

输出如下：