3.Minimum Platforms

Given arrival and departure times of all trains that reach a railway station. Find the minimum number of platforms required for the railway station so that no train is kept waiting. Consider that all the trains arrive on the same day and leave on the same day. Arrival and departure time can never be the same for a train but we can have arrival time of one train equal to departure time of the other.

Example 1:

Input: N = 6 
arr[] = [0900  0940 0950  1100 1500 1800]
dep[] = [0910 1200 1120 1130 1900 2000]
Output: 3
Explanation: 
Minimum 3 platforms are required to 
safely arrive and depart all trains.

Example 2:

Input: N = 3
arr[] = [0900 1100 1235]
dep[] = [1000 1200 1240] 
Output: 1
Explanation: Only 1 platform is required to 
safely manage the arrival and departure 
of all trains. 

Solution: (Efficient Solution)

Approach: Sort the arrival and departure time Check the number of trains arriving at same time

void merge(int arr[], int start, int mid, int end)
{
    vector<int> la;
    vector<int> ra;

    for (int i = start; i <= mid; i++)
    {
        la.push_back(arr[i]);
    }

    for (int i = mid + 1; i <= end; i++)
    {
        ra.push_back(arr[i]);
    }

    int i = 0, j = 0, k = start;
    while (i < la.size() && j < ra.size())
    {
        if (la[i] <= ra[j])
        {
            arr[k] = la[i];
            i++;
        }
        else
        {
            arr[k] = ra[j];
            j++;
        }
        k++;
    }

    while (i < la.size())
    {
        arr[k] = la[i];
        i++;
        k++;
    }

    while (j < ra.size())
    {
        arr[k] = ra[j];
        j++;
        k++;
    }

    return;
}

void sort(int arr[], int start, int end)
{
    if (start >= end)
    {
        return;
    }

    int mid = (start + end) / 2;
    sort(arr, start, mid);
    sort(arr, mid + 1, end);
    merge(arr, start, mid, end);
    return;
}

int findPlatform(int arr[], int dep[], int n)
{

    sort(arr, 0, n - 1);
    sort(dep, 0, n - 1);
    

    int i = 1;
    int j = 0;

    int numPlat = 1;
    int maxPlat = 1;
    while (i < n && j < n)
    {
        if (arr[i] <= dep[j])
        {
            i++;
            numPlat++;
        }
        else if (arr[i] > dep[j])
        {
            numPlat--;
            j++;
        }

        maxPlat = max(numPlat, maxPlat);
    }

    return maxPlat;
}

Time Complexity: O(n log n)