Meeting Rooms easy

Problem Statement

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]] Output: false Explanation: Since [5,10] and [15,20] overlap, it is impossible to attend both meetings.

Example 2:

Input: intervals = [[7,10],[2,4]] Output: true

Steps to Solve

1. Sort the intervals: Sort the intervals based on their start times. This allows us to efficiently check for overlaps.

2. Iterate and check for overlaps: Iterate through the sorted intervals. For each interval, compare its start time with the end time of the previous interval. If the current interval's start time is less than or equal to the previous interval's end time, there's an overlap, and we can immediately return false.

3. No overlaps found: If the iteration completes without finding any overlaps, it means all meetings can be attended, and we return true.

Explanation

The key idea is sorting. By sorting the intervals by start time, we ensure that we're checking for overlaps in a systematic way. We only need to compare each interval with the one immediately preceding it because if there's no overlap between consecutive intervals, there cannot be an overlap between non-consecutive intervals (due to the sorting).

Code (Java)

import java.util.Arrays;

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return true; // No meetings, so no conflicts
        }

        // Sort intervals by start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        // Check for overlaps
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false; // Overlap detected
            }
        }

        return true; // No overlaps found
    }
}

Complexity Analysis

• Time Complexity: O(N log N), dominated by the sorting step. The iteration through the sorted array is O(N).
• Space Complexity: O(log N) or O(N), depending on the implementation of the sorting algorithm. In-place merge sort would be O(log N), while other algorithms might use O(N) extra space. If we ignore the space used by the input array itself, we can consider the space complexity to be O(log N) in a good implementation.