252.Meeting_Rooms(Easy).md

252. Meeting Rooms (Easy)

Date and Time: Nov 21, 2024, 11:40 (EST)

Link: https://leetcode.com/problems/meeting-rooms

Question:

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

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]

Output: false

Example 2:

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

Output: true

Edge Case:

Input: intervals = []

Output: true

Explanation: empty interval can be finished.

Constraints:

• 0 <= intervals.length <= 10^4

• intervals[i].length == 2

• 0 <= start_i < end_i <= 10^6

Walk-through:

1. From the constraint we know, intervals = [] is possible, so we should return True, because empty intervals can be finished.

2. If intervals is not empty, we first sort intervals[] to make sure each meeting's start time is sorted.

3. We create a variable prev to save previous interval's end time, so we can use it to compare with new interval's start time to know if there exists overlap, if prev > start, we should return False.

Python Solution:

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        # First sort intervals
        # If there is overlap between intervals, return False

        # res: [x1, y1], interval: [x2, y2]
        # If x2 < y1, return False
        # Use prev to keep track of previous meeting end time
        # If no overlap and x2 > prev, update prev = y2

        # TC: O(nlogn), n = len(intervals), SC: O(1)
        if not intervals:
            return True
        intervals.sort(key=lambda x: x[0])
        prev = intervals[0][1]
        # Starting after the first interval
        for start, end in intervals[1:]:
            if prev > start:
                return False
            prev = end
        return True

Time Complexity: $O(nlogn)$, because we sort intervals.
Space Complexity: $O(1)$