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

This problem is commonly asked nowadays in Amazon, Facebook and Microsoft interview.Input:[[6,7],[2,4],[8,12]]Output:trueExplanation:None of the meetings overlap with each other.Input:[[1,4],[2,5],[7,9]]Output:falseExplanation:Meetings [1,4] and [2,5] overlap with each other.

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.

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(n ^{2})`, 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.- Initiate a 2-D vector array.
- Add the first interval into it.
- 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.

- 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