...
/Solution: Find the Minimum Platforms Required For a Station
Solution: Find the Minimum Platforms Required For a Station
This review provides a detailed analysis of the solutions to find the number of platforms required for a train station.
We'll cover the following...
Solution 1: brute force
def find_platform(arrival, departure):"""Finds the minimum number of platforms required for a railway Station:param arrival: A list of Arrival Timing:param departure: A list of Departure Timing:return: Minimum number of platforms required for a railway Station"""result = 0count = 0n = len(arrival)for index in range(n):count = 0for i in range(1, n):if arrival[index] <= arrival[i] <= departure[index]:count += 1if result < count:result = countreturn result# Driver code to test above functionif __name__ == '__main__':arrival = [900, 940, 950, 1100, 1500, 1800]departure = [910, 1200, 1120, 1130, 1900, 2000]print(find_platform(arrival, departure))arrival = [200, 210, 300, 320, 350, 500]departure = [230, 240, 320, 430, 400, 520]print(find_platform(arrival, departure))
Explanation
The problem is to find the maximum number of trains that are there on the given railway station at a time. An iterative solution would be to take every interval, one-by-one, and find the number of intervals that overlap with it. Keep track of the maximum number of intervals that overlap with an interval and return the maximum value.
Time complexity
Since this algorithm has two nested independent loops, the time complexity will be ...