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.

The approach is to sort the intervals based on the start time. Then, iterate through the sorted intervals and check if the start time of current interval is less than the end time of previous interval. If it is, then there is an overlap and the person cannot attend all the 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]));
    
    int[] prev = intervals[0];
    for(int i=1; i < intervals.length; i++){
        int[] curr = intervals[i];
        // Check if the start time of current interval 
        // is less than the end time of previous interval
        if(curr[0] < prev[1]){
            return false;
        }
        // Update the previous interval to the current interval
        prev = curr;
    }
    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.