Minimum Number of Platforms Required

Problem Statement: We are given two arrays that represent the arrival and departure times of trains that stop at the platform. We need to find the minimum number of platforms needed at the railway station so that no train has to wait.

Input: N=6,
arr[] = {9:00, 9:45, 9:55, 11:00, 15:00, 18:00}
dep[] = {9:20, 12:00, 11:30, 11:50, 19:00, 20:00}
Output:3

Intuition:

• our goal is find the minimum number of platforms required so that no station waits. this means we have to track the maximum number of trains that are at the station at any point of time. this will give the minimum platforms that we want.

• You are given two arrays:
  arr[]: the arrival times of trains.
  dep[]: the departure times of trains.

how many trains are present at the station at any given moment?

• for each train if it is at the station(hasn't departured), and a new train arrives you need a new platform. So, the task is to check at any moment how many trains overlap (i.e., are at the station at the same time). More overlaps mean more platforms are required.

Sort the trains according to arrival time

• To process the trains in order, you first sort them by their arrival time.
• intially for the first train one platform is needed.
• to keep track of departure times of trains, we will use a min-heap.
• it will help us in finding the train that is departuring soon.

For every train

• compare its arrival time with the departure times of trains that are already at the station (these departure times are stored in the min-heap).
• If the earliest departing train (the one on the top of the heap) has already left (i.e., its departure time is less than the arrival time of the current train), you can remove that train from the heap, freeing up a platform.
• add the current train's departure time to the heap (indicating that the platform is now occupied by the current train).
• at any time the size of heap tells us the how many platforms are occupied.
• so update the ans also to min of previous answer and size of heap.

Code

struct node {
    int arr;
    int dep;
};

// Comparison function to sort trains by arrival times
static bool comp(node a, node b) {
    return a.arr < b.arr;
}

int findPlatform(std::vector<int>& arr, std::vector<int>& dep) {
    int n = arr.size();
    vector<node> temp(n);

    // Initialize the temp array with arrival and departure times
    for (int i = 0; i < n; i++) {
        temp[i].arr=arr[i];
        temp[i].dep=dep[i];
    }

    // Sort the trains by their arrival times
   sort(temp.begin(), temp.end(), comp);

    // Min-heap to track the minimum departure time
    priority_queue<int, vector<int>, greater<int>> pq;

    // Push the first train's departure time
    pq.push(temp[0].dep);

    int ans = 1; // The minimum number of platforms required (at least 1)

    // Iterate over the rest of the trains
    for (int i = 1; i < n; i++) {
        // Remove all trains that have already departed by the time the current train arrives
        while (!pq.empty() && pq.top() < temp[i].arr) {
            pq.pop();
        }

        // Push the current train's departure time
        pq.push(temp[i].dep);

        // Update the answer with the maximum size of the heap (i.e., the maximum number of overlapping trains)
        ans = max(ans, (int)pq.size());
    }

    return ans;
}

Time Complexity:
Sorting: O(n log n), where n is the number of trains.
Heap Operations: Each train involves push and possibly pop operations, which are O(log n) per train. Thus, this part also takes O(n log n).