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 Explanation: There is no overlap between meetings.

Steps to Solve

  1. Sort the intervals: Sort the intervals based on their start times. This makes it easier to 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 you can immediately return false.

  3. No Overlaps: If you iterate through all intervals without finding any overlaps, it means all meetings can be attended, so return true.

Explanation

The core idea is that if we sort the intervals by start time, any overlap will be directly adjacent. We only need to compare each interval's start time to the end time of the immediately preceding interval. If a start time is before the previous end time, there's a conflict.

Code (Typescript)

function canAttendMeetings(intervals: number[][]): boolean {
    //Sort intervals based on start time.
    intervals.sort((a, b) => a[0] - b[0]);

    //Iterate and check for overlaps
    for (let i = 1; i < intervals.length; i++) {
        //Check if current meeting's start time is before previous meeting's end time.
        if (intervals[i][0] < intervals[i - 1][1]) {
            return false; //Overlap found
        }
    }

    return true; //No overlaps found
}

Complexity Analysis

  • Time Complexity: O(n log n), dominated by the sorting step.
  • Space Complexity: O(1) if we can modify the input array in place (which is allowed by LeetCode), otherwise O(n) for creating a copy to sort. The extra space used by the loop is constant, O(1).