Meeting Rooms

Problem Statement

The task is to determine whether a person can attend all specified meetings based on their given intervals. Each meeting time is described by an array where intervals[i] = [starti, endi], representing the start and end time of the i-th meeting. The objective is to identify any overlapping intervals, which would indicate that it is impossible for the person to attend all meetings simultaneously. To solve this, one needs to evaluate whether any meeting times conflict with others in the array.

Examples

Example 1

Input:

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

Output:

false

Example 2

Input:

intervals = [[7,10],[2,4]]

Output:

true

Constraints

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti < endi <= 106

Approach and Intuition

To determine if a person can attend all the meetings without any conflicts, follow these considerations:

1. Sort the intervals based on the start times. Sorting helps in easily comparing the end time of one meeting to the start time of the next meeting in the list.

2. Traverse through the sorted intervals and compare the end time of the current meeting with the start time of the next meeting:

   • If the end time of one meeting is greater than the start time of the subsequent meeting, it means there is an overlap, and the person cannot attend both meetings. Hence, return false.
   • Continue this till the end of the array. If no overlaps are found, return true.

Let's apply this approach to the given examples:

• Example 1:

  • For intervals = [[0,30],[5,10],[15,20]], when sorted by start times remains [[0,30], [5,10], [15,20]]. It's evident that the meeting from 0 to 30 overlaps with the other two meetings. Therefore, the expected outcome is false.

• Example 2:

  • The sorted order for intervals = [[7,10],[2,4]] based on start times is [[2,4], [7,10]]. There is no overlap between [2,4] and [7,10] since the end time of the first meeting (4) is less than the start time of the second meeting (7). Hence, the expected answer is true.

This method is efficient, with the primary overhead being the time taken to sort the intervals, which is generally O(n log n). Once sorted, the check for overlap can be accomplished in linear time, O(n), leading to an overall time complexity of O(n log n). Given the constraints, this approach is computationally feasible.

Solutions

class Solution {
public:
    bool isPossibleToAttend(vector<vector<int>>& timetable) {
        if (timetable.empty()) {
            return true;
        }
    
        // Sorting the timetable by start times
        sort(timetable.begin(), timetable.end());
        for (size_t index = 0; index < timetable.size() - 1; index++) {
            // Check for overlap
            if (timetable[index][1] > timetable[index + 1][0]) {
                return false;
            }
        }
        return true;
    }
};