Minimum Platforms

In this blog:

• Understanding the problem statement
• Approach
• Dry Run
• Code
• Understanding the complexity
• Similar Problems to try

Understanding the problem Statement

https://www.geeksforgeeks.org/problems/minimum-platforms-1587115620/1

en arrival arr[] and departure dep[] times of trains on the same day, find the minimum number of platforms needed so that no train waits. A platform cannot serve two trains at the same time; if a train arrives before another departs, an extra platform is needed.

Note: Time intervals are in the 24-hour format (HHMM) , where the first two characters represent hour (between 00 to 23 ) and the last two characters represent minutes (this will be <= 59 and >= 0). Leading zeros for hours less than 10 are optional (e.g., 0900 is the same as 900).

Examples:

Input: arr[] = [900, 940, 950, 1100, 1500, 1800], dep[] = [910, 1200, 1120, 1130, 1900, 2000]
Output: 3
Explanation: There are three trains during the time 9:40 to 12:00. So we need a minimum of 3 platforms.

Input: arr[] = [900, 1235, 1100], dep[] = [1000, 1240, 1200]
Output: 1
Explanation: All train times are mutually exclusive. So we need only one platform.

Input: arr[] = [1000, 935, 1100], dep[] = [1200, 1240, 1130]
Output: 3
Explanation: All 3 trains have to be there from 11:00 to 11:30

Constraints: 1 ≤ number of trains ≤ 1e5 0000 ≤ arr[i] ≤ dep[i] ≤ 2359

Imagine we are at a Train station where trains come and go at their designated time if Platform 1 is acquired by Train 1 from 9:00 to 9:30 and Train 2 is arriving at 9:25 so we have direct it to another platform say platform 2 now it will stay there till 9:45 now Train 3 arrives at the station at 9:40 but platform 2 is occupied so will we direct Train 3 to platform 3? No, we will use platform 1 as Train 1 has already left.

So, we required 2 platforms to place these 3 trains.

Approach

As we need to place all trains in the minimum number of platform. The keyword here is minimum so we need to be greedy while placing trains as we do not want to waste our resources.

So we would need to place the early trains first so we should sort our arrival and departure time.

We need to keep track of the platforms so why don’t we increment our platform count when a train arrives and decrement it when the train leaves?

“A platform cannot be used for two trains at the same time.”

If one train departs at 9:40 and another arrives at 09:40, they are considered overlapping and require two platforms.

Therefore, when times are equal:

Arrival must be processed before Departure.

and we keep the max platform needed at any time

How does this work?

Dry Run

let’s take an example

Train 1- 9:00 to 9:40

Train 2- 9:40 to 12:00

Train 3- 9:50 to 11:20

Train 4- 11:00 to 11:30

Train 5- 15:00 to 19:00

Train 6- 18:00 to 20:00

Step 1: let’s sort

9:00(A) 9:40(A) 9:40(D) 9:50(A) 11:00(A) 11:20(D) 11:30(D) 12:00(D) 15:00(A) 18:00(A) 19:00(D) 20:00(D)

Step 2: Arrival -> platform ++ , Departure->platform — —

9:00(A) platform=1 ,max=1

9:40(A) platform=2, max=2

9:40(D) platform=1, max= 2

9:50(A) platform=2, max=2

11:00(A) platform=3, max=3

11:20(D) platform=2, max=3

11:30(D) platform=1, max=3

12:00(D) platform= 0, max=3

15:00(A) platform=1, max=3

18:00(A) platform =2, max=3

19:00(D) platform=1, max=3

20:00(D) platform=0, max=3

So, the total number of platform required is 3.

Code

class Solution {
  public:
    int minPlatform(vector<int>& arr, vector<int>& dep) {
        vector<pair<int,int>>train(2*arr.size());

        for(int i=0;i<arr.size();i++){
            train[2*i].first=arr[i];
            train[2*i].second=1;
            train[2*i+1].first=dep[i];
            train[2*i+1].second=-1;
        }

        sort(train.begin(), train.end(), [](auto &a, auto &b){
    if(a.first == b.first)
        return a.second > b.second;   // +1 before -1
    return a.first < b.first;
});

        int platform=0;
        int m=0;
        for(int i=0;i<train.size();i++){
            platform+=train[i].second;
            m=max(platform,m);
        }
        return m;
    }
};

Time complexity

arr.size()=n;

dep.size()=n;

Total size= 2n

Sorting= O(nlogn)

Calculating platform= O(2n) = O(n)

Total Complexity: O(n logn + n) = O(nlogn)

Similar problems

Meeting rooms II :https://leetcode.com/problems/meeting-rooms-ii/description/

Merge intervals: https://leetcode.com/problems/merge-intervals/description/

(uses sweep line algorithm) The skyline problem:https://leetcode.com/problems/the-skyline-problem/