Meeting Rooms

Problem Statement

LeetCode-252: Given an array of meeting time intervals intervals where $intervals[i] = [start_i, end_i]$, determine if a person could attend all meetings.

Approach

The problem is to check if there are any overlapping intervals. If there are overlapping intervals, then the person cannot attend all the meetings.

A few points to note:

1. Zero intervals is a valid case given by the constraints.
2. If there is only one interval or no intervals, then the person can attend the meeting.
3. The intervals are not sorted.

To determine if the meeting time intervals overlap, we can follow the below approach:

1. Sort the intervals by start time. This way, each meeting is arranged in the order they occur.
2. Check adjacent meetings by iterating through the sorted intervals and compare the start time of the current meeting with the end time of the previous meeting. If the current meeting starts before the previous meeting ends, there is an overlap, and the person cannot attend both meetings.

Implementation

Here is a java implementation of the approach:

public boolean canAttendMeetings(int[][] intervals) {
    if(intervals.length < 2){
        return true;
    }
    // Sort the intervals based on the start time    
    Arrays.sort(intervals, (one,two) -> Integer.compare(one[0], two[0]));   
    
    for(int i=1; i < intervals.length; i++){
        if(intervals[i][0] < intervals[i-1][1]){
            return false;
        }
    }
    return true;
}

Complexity Analysis

The time complexity for this approach is $O(n \log n)$, where $n$ is the number of intervals. The complexity is due to sorting the intervals based on the start time. As the sorting is done in-place, the space complexity is $O(1)$.