Minimum Number of Platforms
In this class, We discuss the Minimum Number of Platforms.
The reader can study complete competitive coding. Click Here.
For Complete YouTube Video: Click Here
Question:
They provide the arrival and departure times of N trains.
The below diagram shows an example timings of six trains.
Conditions:
1) If the arrival of one train is equal to another train’s departure, then assign a new platform.
2) The arrival time of the train is always less than the departure time
3) All trains arrive and depart on the same day
We need to find the minimum number of platforms required to schedule the trains.
Time complexity = O(nlogn)
Space complexity = O(1)
The above example needed a minimum of three platforms to schedule the trains.
Output = 3
We use a similar logic from the merge sort algorithm.
Merge logic in merge sort
We have two sorted lists, and we need to bring a new sorted list by merging the two sorted lists.
The below diagram shows the example.
The logic for Minimum number of platforms
First, sort the elements in the arrival and departure list.
The below diagram shows the procedure and conditions.
The step-by-step explanation is provided in the video mentioned above.
Code:
class Solution:
def minimumPlatform(self,n,arr,dep):
dep.sort()
arr.sort()
i=1
j=0
result=1
platform=1
while(i<n and j<n):
if arr[i]<=dep[j]:
i+=1
platform+=1
elif arr[i]>dep[j]:
j+=1
platform-=1
if result<platform:
result=platform
return result
n=int(input())
arrival=list(map(int,input().strip().split()))
departure=list(map(int,input().strip().split()))
ob=Solution()
print(ob.minimumPlatform(n,arrival,departure))