Q12:Given arrival and departure times of all trains that reach a railway station. Find the minimum number of platforms required for the railway station so that no train is kept waiting.
Consider that all the trains arrive on the same day and leave on the same day. Arrival and departure time can never be the same for a train but we can have arrival time of one train equal to departure time of the other. At any given instance of time, same platform can not be used for both departure of a train and arrival of another train. In such cases, we need different platforms.
Example :
Input: n = 6
arr[] = {0900, 0940, 0950, 1100, 1500, 1800}
dep[] = {0910, 1200, 1120, 1130, 1900, 2000}
Output: 3
Explanation:
Minimum 3 platforms are required to
safely arrive and depart all trains.
Solution:
class Solution{
public:
int findPlatform(int arr[], int dep[], int n)
{
int maxi=0;
int count=0;
sort(arr,arr+n);
sort(dep,dep+n);
int i=0,j=0;
while(i<n && j<n)
{
if(arr[i]<=dep[j])
{
count++;
i++;
}
else
{
count--;
j++;
}
maxi=max(count,maxi);
}
return maxi;
}
};
Explaintion:
>Code Overview:
The solution is implemented as a member function named findPlatform within a class.
It takes three parameters: an array of arrival times (arr), an array of departure times (dep),
and the number of trains (n).
Returns the maximum number of platforms needed.
>Sorting Arrival and Departure Times:
The arrival (arr) and departure (dep) arrays are sorted in ascending order.
Sorting allows for a simplified comparison between arrival and departure times.
>Platform Calculation using Two-Pointer Approach:
Two pointers (i and j) are used to traverse the sorted arrays of arrival and departure times.
Initialize variables count to keep track of the number of trains currently at the station
and maxi to store the maximum count of trains at any point.
>Iteration through the Arrays:
While both pointers are within the array bounds:
If the arrival time at arr[i] is less than or equal to the departure time at
dep[j], a train has arrived. Increment the count, move the arrival pointer (i) forward.
If the departure time at dep[j] is greater, a train has departed. Decrement the count,
move the departure pointer (j) forward.
Update maxi with the maximum count encountered during iteration.
>Maximum Platforms:
The final value of maxi represents the maximum number of platforms needed at any point.
>Time Complexity:
O(n log n) due to the sorting step.
>Space Complexity:
O(1) as the sorting is done in-place.
>Key Concept:
The two-pointer approach efficiently handles the chronological order of train
arrivals and departures to calculate the maximum number of platforms needed.
>Edge Cases:
The code assumes a valid input with matching arrival and departure times.
It provides an optimal solution for determining the platform requirements at the railway station.