Minimum Platforms — HackerRank
Hello all,
This article is about solving the problem that is mentioned in the below link
There are standard solutions available online that discuss about the different approaches for this problem. You can visit the below link to check it out.
The solution approach that i’m going to explain below is not about the standard ones. Okay, let us dive into the problem.
In this problem, we have a list of trains with their arrival and departure time. We have to count the minimum number of platforms needed in the station so that no train waits.
Let us take an example, if we have trains with their timing like this:
train1 — {arrival : 9 AM, departure : 10AM}
train2 — {arrival : 9.30AM, departure : 10AM}
If we have only one platform in our station, then train2 have to wait till train1 leaves the station. So we need at least two platforms in this case to run those trains without waiting. So the output of the above scenario will be two.
Prerequisites
- Sorting algorithm.
- Priority Queues.
Intuition
Let us go through the above example and derive some facts,
- If the arrival time of a train is less than the departure time of the preceding trains, then we need a platform.
- If the trains aren’t ordered based on the starting time, then we will be in chaos. Just take an example of unordered trains, give it a try.
Solution Approach
Step 1 : Since unordered trains won’t help, first step is to sort the trains based on their starting time. Sorting ( Merge Sort or Quick Sort).
Step 2 : We need the minimum departure time of the preceding trains (Note : Not a single train that moves before the current train. All the trains that went before the current train). How can we maintain it ? Priority Queues(Min Heap).
These are the two main steps that has been used.
Code
I have done the code part in C language. I try to add the java snippet ASAP.
- We will sort the trains based on the arrival time of the trains(Use Merge Sort or Quick Sort). I have used merge sort.
// st - Arrival Time of the train.
// et - Departure Time of the train.void merge(int st[],int et[],int start,int mid,int end){
int p = start,q = mid + 1;
int arr[end-start+1],arr1[end-start+1],k = 0,i;
for(i = start;i <= end;i++){
if(q > end){
arr[k] = st[p];
arr1[k++] = et[p++];
}
else if(p > mid){
arr[k] = st[q];
arr1[k++] = et[q++];
}
else if(st[p] < st[q]){
arr[k] = st[p];
arr1[k++] = et[p++];
}
else if(st[p] > st[q]){
arr[k] = st[q];
arr1[k++] = et[q++];
}
else if(et[p] < et[q]){
arr[k] = st[p];
arr1[k++] = et[p++];
}
else{
arr[k] = st[q];
arr1[k++] = et[q++];
}
}
for(p = 0;p < k;p++){
st[start] = arr[p];
et[start++] = arr1[p];
}
}void mergesort(int st[],int et[],int start,int end){
if(start < end){
int mid = (start + end) / 2;
mergesort(st,et,start,mid);
mergesort(st,et,mid + 1,end);
merge(st,et,start,mid,end);
}
}
- Next we need to keep track of the minimum departure time of the previous trains. So that we can use the same platforms.
- We will initialise the priority queue with no trains initially. Util methods to use the queue.
// Heap array will act as a priority queue
// count specifies the number of elements in the queue
// Any position lets say i, its parent will be in (i - 1) / 2
// Left Child is (2 * i) + 1 and right child is (2 * i) + 2int heap[100], count = 0;// Checks whether the heap is empty or not.
int isHeapEmpty(){
if(count == 0)
return 1;
else
return 0;
}// Inserts the element into the queue. Checks if the current value // is less than its parent. If so swap with its parent and goes up.void insert(int val){
int pos = count;
count++;
while(pos > 0 && val < heap[(pos - 1) / 2]){
heap[pos] = heap[(pos - 1) / 2];
pos = (pos - 1) / 2;
}
heap[pos] = val;
}// Gets the minimum element.int peek(){
return heap[0];
}// Checks its branches and ensure the heap property.
void heapify(int pos){
int leftChild = (2 * pos) + 1;
int rightChild = (2 * pos) + 2;
int max = pos;
if(leftChild < count && rightChild < count){
max = heap[leftChild] < heap[rightChild] ? leftChild : rightChild;
}
else if(leftChild < count){
max = leftChild;
}
else if(rightChild < count)
max = rightChild;
if(pos != max){
heap[pos] = heap[max];
heapify(max);
}
}// Deletes the minimum element and adjust the queue.
void deleteMin(){
heapify(0);
count--;
}
- Now we will process the trains one by one. If the heap is empty, then we will increase the result and add the current train’s departure time to the heap. This case will happen for the first train alone. Now the heap will contain the departure time of the first train alone.
- We process the next train. If the minimum departure time of the train in the heap is less than the current train arrival time, then we can use the same platform. So we will remove the minimum time of the preceding train from heap and add the current train’s departure time.
- If the minimum departure time in the heap is not less means we have to add a new platform and insert the current train’s departure time into the heap.
// st - Start time of the trains
// et - End time of the trains
// res - Number of platforms
// N - Number of trainsint res = 0;
for(i = 0;i < N;i++){
if(!isHeapEmpty() && peek() < st[i]) {
deleteMin();
insert(et[i]);
}
else {
res++;
insert(et[i]);
}
}
printf("%d\n",res);
Example
Let us take an example and walk through the solution. For the sake of simplicity, i’m using the railway timings.
Input :
Arrival = {9,11,13,10,5}
Departure = {12,14,16,15,7}
Output : 3
So the sorted trains will be like this : Arrival{5,9,10,11,13} , Departure{7,12,15,14,16}
After 1st train : Train 1 (5, 7). Heap is empty so there is no existing free platforms.Add a platform( P = 1). Add the departure time of the current train to the heap. Heap now contains 7.
After 2nd train : Train 2 (9,12). Heap is not empty. Check with minimum value from the heap. MinValue in heap = 7. MinValue in heap is less than current train’s arrival time (7 < 9). Yes, now use the same platform. Delete the minimum from heap and insert the current train’s departure time to the heap. So heap will contain 12 now.
After 3rd train : Train 3 (10,15). Heap is not empty. Do the check (12 < 10). No its not, so increase the platform count (P = 2). Add the current train’s departure time to the heap. So heap now contains 12,15.
After 4th train : Train 4 (11,14). Heap is not empty. Do the check (12 < 11).Repeat the process(P = 3). Now heap contains 12,14,15.
After 5th train : Train 5 (13,16). Heap is not empty. Do the check(12 < 13).We can use the platform where the 2nd train came. So we just delete the 2nd train from heap. Add the current train’s departure time in the heap. Now the heap contains 14,15,16.
Right now we have processed all the trains. Print the platforms count.
Entire code :
int main() {
int N,res = 0;
scanf("%d",&N);
int st[N],et[N],i;
for(i = 0;i < N;i++)
scanf("%d %d",&st[i],&et[i]); mergesort(st,et,0,N-1);
for(int i = 0;i < N;i++){
printf("%d %d\n",st[i],et[i]);
}
for(i = 0;i < N;i++){
if(!isHeapEmpty() && peek() < st[i]){
deleteMin();
insert(et[i]);
}
else{
res++;
insert(et[i]);
}
}
printf("%d\n",res);
return 0;
}
Complexities Discussion
Time Complexity : O(N log N). O(N log N) for sorting + O(N log N) for each element insertion into the heap in the worst case.
Space Complexity : O(N). N elements in the heap.
I hope the above explanation will help you to solve the problem. If you have any doubts or any suggestions or find any mistakes in the above post, please mention it in the comments.
Thanks everyone.
📝 Read this story later in Journal.
👩💻 Wake up every Sunday morning to the week’s most noteworthy stories in Tech waiting in your inbox. Read the Noteworthy in Tech newsletter.
