Meeting Rooms

Given an array of intervals representing N meetings, find out if a person can attend all the meetings.

Input:
[[6,7],[2,4],[8,12]]
Output:
true
Explanation:
None of the meetings overlap with each other.

Input:
[[1,4],[2,5],[7,9]]
Output:
false
Explanation:
Meetings [1,4] and [2,5] overlap with each other.
This problem is commonly asked nowadays in Amazon, Facebook and Microsoft interview.


Thought Process

A person can not attend two or more meetings at one time. It means if the timings of two meetings are overlapping, then she/he will not able to attend it.
Now, the question comes in your mind that How to recognize/check that the two meetings are overlapping or not. We will use the time interval to check that the meetings are overlapping or not.

Follow below picture to get to know about overlapping.

Meeting Rooms
These are are the 4 Overlapping Situations.

Now, we have to check if one meeting interval is overlapping with other, then it is impossible to attend that meeting.

Brute Force

The Simple Solution is to compare every two meetings using the nested for loop and to check whether the intervals are overlapping or not. Two meetings overlap if one meeting is going on and other meeting starts before finishing the first meeting.

class Solution {
public:
    bool check_overlap(vector<int>first, vector<int>second)
    {
        if((first[0]>=second[0] && first[0]<second[1]) 
           || (second[0]>=first[0] && second[0] <first[1])){
            return true;
        }
        return false;
    }
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        int i,j;
        
        for(i=0;i<intervals.size();i++)
        {
            for(j=i+1;j<intervals.size();j++)
            {
                if(check_overlap(intervals[i],intervals[j]))
                {
                    return false;
                }
            }
        }
        return true;
    }
};

Time Complexity of the brute force implementation is O(n2), due to nested for loop where as space complexity is O(1)

Using Merge Intervals Technique

In this, what we do is we merge all the overlapping intervals. After Merging, we compare the number of intervals before merging and after merging. If the number of intervals is the same, then there are no conflicts in the meetings, it will run smoothly(no overlapping situation). If the total number of intervals are less after merging, then it means there were some overlapping intervals, so there will be conflicts in meetings.

If you wan to learn merging intervals in detail, go here.

First, Sort the intervals in ascending order.
  1. Initiate a 2-D vector array.
  2. Add the first interval into it.
  3. for every other intervals
    • check if the last interval in the vector array is overlapping with current interval, then pop the last interval from vector array and merge the both intervals and push it in the vector array.
    • check if the last interval in he vector array is not overlapping with current interval, push current interval in the vector array.
  4. if(size of vector array formed < size of initial intervals array given)
    • return false
    • else return true;
class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        int i,j;
        
        vector<vector<int>>v;
        if(intervals.size()==0)
        {
            return true;
        }
        sort(intervals.begin(), intervals.end());
        vector<int>l;
        l.push_back(intervals[0][0]);
        l.push_back(intervals[0][1]);
        v.push_back(l);
        
        for(i=1;i<intervals.size();i++)
        {
            vector<int> prev=v.back();
            //time to merge
            if(intervals[i][0]<prev[1])
            {
                l.clear();
                v.pop_back();
                l.push_back(prev[0]);
                l.push_back(max(prev[1],intervals[i][1]));
                v.push_back(l);
            }
            else
            {
                v.push_back(intervals[i]);
            }
        }
        if(intervals.size()==v.size())
        {
            return true;
        }
        return false;
        
    }
};

The time complexity is O(nlogn) and space complexity is O(n)

Sorting

what we do here is that we sort the array in ascending order. After sorting, we compare the meeting with the previous meeting and make sure that the meeting should not overlap. If it overlaps, return false otherwise return true.

class Solution {
    static bool compare(vector<int>v1, vector<int>v2) {
        return v1[0] == v2[0] ? v1[1] > v2[1] : v1[0] < v2[0];
    }
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        
        sort(intervals.begin(), intervals.end(), compare);
        
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i-1][1] > intervals[i][0])
                return false;
        }
        
        return true;
    }
};

The time Complexity is O(nlogn) and space complexity is O(1)

Please write to us if something is missing or wrong, we will be happy to fix it.

This article is contributed by Monika Bhasin