-
Notifications
You must be signed in to change notification settings - Fork 77
/
Minimum_number_of_platforms_required_for_a_railway.cpp
50 lines (40 loc) · 1.54 KB
/
Minimum_number_of_platforms_required_for_a_railway.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// Problem Statement: We are given two arrays that represent the arrival and departure times of trains that stop at the platform. We need to find the minimum number of platforms needed at the railway station so that no train has to wait.
// Examples 1:
// Input: N=6,
// arr[] = {9:00, 9:45, 9:55, 11:00, 15:00, 18:00}
// dep[] = {9:20, 12:00, 11:30, 11:50, 19:00, 20:00}
// Output:3
// Explanation: There are at-most three trains at a time. The train at 11:00 arrived but the trains which had arrived at 9:45 and 9:55 have still not departed. So, we need at least three platforms here.
// Example 2:
// Input Format: N=2,
// arr[]={10:20,12:00}
// dep[]={10:50,12:30}
// Output: 1
// Explanation: Before the arrival of the new train, the earlier train already departed. So, we don’t require multiple platforms.
#include<bits/stdc++.h>
using namespace std;
int countPlatforms(int n,int arr[],int dep[])
{
int ans=1; //final value
for(int i=0;i<=n-1;i++)
{
int count=1; // count of overlapping interval of only this iteration
for(int j=i+1;j<=n-1;j++)
{
if((arr[i]>=arr[j] && arr[i]<=dep[j]) ||
(arr[j]>=arr[i] && arr[j]<=dep[i]))
{
count++;
}
}
ans=max(ans,count); //updating the value
}
return ans;
}
int main()
{
int arr[]={900,945,955,1100,1500,1800};
int dep[]={920,1200,1130,1150,1900,2000};
int n=sizeof(dep)/sizeof(dep[0]);
cout<<"Minimum number of Platforms required "<<countPlatforms(n,arr,dep)<<endl;
}