6.Meeting Rooms

Given an 2D integer array A of size N x 2 denoting time intervals of different meetings.

Where:

A[i][0] = start time of the ith meeting.

A[i][1] = end time of the ith meeting.

Find the minimum number of conference rooms required so that all meetings can be done

Example Input
Input 1:

 A = [      [0, 30]
            [5, 10]
            [15, 20]
     ]

Input 2:

 A =  [     [1, 18]
            [18, 23]
            [15, 29]
            [4, 15]
            [2, 11]
            [5, 13]
      ]


Example Output
Output 1:
2

Output 2:
4

Solution: (Similar to no of platform)/ (Can be solved using similar approach as carpooling)

int Solution::solve(vector<vector<int>> &A)
{

    vector<int> st;
    vector<int> et;

    for (int i = 0; i < A.size(); i++)
    {
        st.push_back(A[i][0]);
        et.push_back(A[i][1]);
    }

    sort(st.begin(), st.end());
    sort(et.begin(), et.end());

    int numRooms = 1;
    int maxRooms = 1;

    int i = 1, j = 0;

    while (i < st.size() && j < et.size())
    {

        if (st[i] < et[j])
        {
            i++;
            numRooms++;
        }
        else if (st[i] >= et[j])
        {
            j++;
            numRooms--;
        }

        maxRooms = max(numRooms, maxRooms);
    }

    return maxRooms;
}

Time Complexity: O(n log n)

Using Priority Queue

int Solution::solve(vector<vector<int>> &A)
{

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    for (int i = 0; i < A.size(); i++)
    {
        pq.push({A[i][0], 1});
        pq.push({A[i][1], -1});
    }

    int numRooms = 0;
    int maxRooms = 0;

    while (!pq.empty())
    {
        int c = pq.top().second;
        pq.pop();
        
        numRooms += c;

        maxRooms = max(maxRooms, numRooms);
    }

    return maxRooms;
}

Time Complexity: O(n log n)