Two Pointers: Meeting rooms

Problem Statement:

You are given 2 arrays start[] and end[].

Start[i] gives the start of the meeting and end[i] gives the end of the meeting.

You need to find the minimum rooms required to attend all the meetings.

Example:

Input:

start [] = [2, 11, 8]
end[] = [5, 16, 11]

Output: 1

All the meetings are held at different times, only 1 meeting room is sufficient

Solution 1: Bruteforce approach

You can use 2 nested loops that go through start and end times and identfy the overlap.

Then check for each meeting how many other meetings are taking place in the room at the same time and max of all the meeting will be the result.

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution 2: 2 pointers approach

In this approach, we will sort both the arrays.

Then take 2 pointers to traverse through both the arrays and find the minimum rooms required.

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> &start, vector<int> &end) 
{  
    int n = start.size();

    int room = 1;
    int res = 1;
    
    for (int i = 0; i < n; i++) 
    {
        room = 1;
        for (int j = 0; j < n; j++) 
        {
            if (i != j)
                if (start[i]>= start[j] && end[j]>start[i])
                    room++;
        }

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

int solution_2(vector<int> &start, vector<int> &end) 
{
    int n = start.size();

    int room = 0;
    int res = 0;

    sort(start.begin(), start.end());
    sort(end.begin(), end.end());

    int i = 0;
    int j = 0;

    while (i < start.size()) 
    {

        if (start[i] < end[j]) 
        {
            room++;
            i++;
        }

        else 
        {
            room--;
            j++;
        }
        res = max(res, room);
    }
    return res;
}

int main() 
{
    
    vector<int>start= {2, 11, 8};
    vector<int>end = {5, 16, 11};

    cout << solution_1(start,end)<<endl;
    cout << solution_2(start,end);
    return 0;
}

Output

1
1