Minimum Number of Platforms Required for a Railway/Bus Station - GeeksforGeeks
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 waits.
We are given two arrays which represent arrival and departure times of trains that stop
http://www.crazyforcode.com/min-number-platforms-required-railway-station/
Read full article from Minimum Number of Platforms Required for a Railway/Bus Station - GeeksforGeeks
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 waits.
We are given two arrays which represent arrival and departure times of trains that stop
We can solve the above problem in O(nLogn) time. The idea is to consider all evens in sorted order. Once we have all events in sorted order, we can trace the number of trains at any time keeping track of trains that have arrived, but not departed.
Note that the implementation doesn’t create a single sorted list of all events, rather it individually sorts arr[] and dep[] arrays, and then uses merge process of merge sort to process them together as a single sorted array.
How we represent data here: if input is a list of TrainSchedule(start,end):
we can add 2 events, one arrive, one depart, and one flag to distinguish them. Then sort them.
-- As in this post, it's better we have 2 Array, one for arrive, one for departure, and merge them.
How we represent data here: if input is a list of TrainSchedule(start,end):
we can add 2 events, one arrive, one depart, and one flag to distinguish them. Then sort them.
-- As in this post, it's better we have 2 Array, one for arrive, one for departure, and merge them.
int
findPlatform(
int
arr[],
int
dep[],
int
n)
{
// Sort arrival and departure arrays
sort(arr, arr+n);
sort(dep, dep+n);
// plat_needed indicates number of platforms needed at a time
int
plat_needed = 1, result = 1;
int
i = 1, j = 0;
// Similar to merge in merge sort to process all events in sorted order
while
(i < n && j < n)
{
// If next event in sorted order is arrival, increment count of
// platforms needed
if
(arr[i] < dep[j])
{
plat_needed++;
i++;
if
(plat_needed > result)
// Update result if needed
result = plat_needed;
}
else
// Else decrement count of platforms needed
{
plat_needed--;
j++;
}
}
return
result;
}
Read full article from Minimum Number of Platforms Required for a Railway/Bus Station - GeeksforGeeks