Sorting: Given 2 arrays, return minimum number of platforms required for a railway station

Problem Statement:

You are given 2 arrays arrival[], departure[] of trains.

You need to get the minimum number of platforms required, so that no train has to wait

Example:

Input: 
arr[] = [10, 13, 12, 13, 16, 18]
dep[] = [12, 15, 15, 15, 17, 19]

Output:

3

There are 3 trains from 13 to 15. 
Hence we need 3 platform

Solution 1: Bruteforce approach

In this approach we will use 2 nested loops.

Then we will check how many trains have overlapping with the arrival and departure time.

Increment the count and then return the result.

Time Complexity: O(n*n)
Space Complexity: O(1)

Solution 2: Sorting approach

We will use sorting and two pointer approach.

we will first sort the array of both arrival and departure time.

Then traverse through the both arrays with help of 2 pointers

Time Complexity: O(n logn)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution_1 (vector<int> &arr, vector<int>& dep) 
{

    int n = arr.size();
    int res = 0;

    for (int i = 0; i < n; i++) 
    {

        int count = 1;
        for (int j = 0; j < n; j++) 
        {
            if (i != j)
                
                if (arr[i] >= arr[j] && dep[j] >= arr[i])
                    count++;
        }

        res = max(count, res);
    }
    return res;
}

int solution_2(vector<int> &arr, vector<int>& dep) 
{
    int n = arr.size();
    int res = 0;

    sort(arr.begin(), arr.end());
    sort(dep.begin(), dep.end());
    
    int j = 0;

    int count = 0;
    
    for (int i=0; i<n; i++) 
    {
        
        while (j<n && dep[j]<arr[i]) 
        {
            count--;
            j++;
        }
        
        count++;
        
        res = max(res, count);
    }
    
    return res;
}

int main() 
{

    vector<int> arr = {10, 13, 12, 13, 16, 18};
    vector<int> dep = {12, 15, 15, 15, 17, 19};
    cout << "Solution 1 = " <<solution_1(arr, dep)<<endl;
    cout << "Solution 1 = " <<solution_2(arr, dep);
    return 0;
}

Output

Solution 1 = 3
Solution 1 = 3