...

/

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.

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 = 0
count = 0
n = len(arrival)
for index in range(n):
count = 0
for i in range(1, n):
if arrival[index] <= arrival[i] <= departure[index]:
count += 1
if result < count:
result = count
return result
# Driver code to test above function
if __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 ...