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 not possible to attend all meetings.

Example 2

Input: intervals = [[7,10],[2,4]] Output: true Explanation: Since the meetings do not overlap, it is possible to attend all meetings.

Steps

1. Sort the intervals: Sort the intervals based on their start times. This makes it easier to check for overlaps.

2. Iterate and compare: 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 return false.

3. Return true: If the loop completes without finding any overlaps, it means all meetings can be attended, so we return true.

Explanation

The key idea is to sort the intervals by their start times. Sorting allows us to efficiently check for overlaps by comparing only adjacent intervals. If we find any overlap (current start time <= previous end time), it means we cannot attend all meetings. Otherwise, we can attend all meetings.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public bool CanAttendMeetings(int[][] intervals) {
        if (intervals == null || intervals.Length == 0) return true;

        // Sort intervals by start time
        Array.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 found
            }
        }

        return true; // No overlaps found
    }
}

Complexity

• Time Complexity: O(n log n), dominated by the sorting step.
• Space Complexity: O(1) (In-place sorting can be used, and only a constant amount of extra space is used). If the sorting algorithm used has additional space complexity, that would need to be considered. However, many efficient sorting algorithms have O(log n) space complexity.