LeetCode 252: Meeting Rooms - Complete Solutions Guide

Problem Statement

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

Copy codeInput: intervals = [[0,30],[5,10],[15,20]]
Output: false
Explanation: Cannot attend all meetings due to overlap between [5,10] and [0,30]

Input: intervals = [[7,10],[2,4]]
Output: true
Explanation: No overlapping meetings

Solution 1: Brute Force Comparison

Explanation

Compare every meeting with every other meeting to check for overlaps: 1. Nested Loop: For each interval, compare with all others 2. Overlap Check: Two intervals overlap if one starts before the other ends

Step-by-Step Example

For intervals = [[0,30],[5,10],[15,20]]: 1. [0,30] overlaps with [5,10] → return false

Python Code

Copy codeclass Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        for i in range(len(intervals)):
            for j in range(i+1, len(intervals)):
                # Check if intervals overlap
                if (intervals[i][0] < intervals[j][1] and 
                    intervals[i][1] > intervals[j][0]):
                    return False
        return True

Complexity

• Time: O(n²) - All pairs comparison
• Space: O(1)
• Pros: Simple logic
• Cons: Too slow for large inputs

Solution 2: Sorting and Checking (Optimal)

Explanation

Sort meetings by start time, then check adjacent pairs: 1. Sort: Arrange intervals by start time 2. Single Pass: Check if any interval starts before previous ends

Step-by-Step Example

For intervals = [[0,30],[5,10],[15,20]]: 1. Sorted: [[0,30],[5,10],[15,20]] 2. Compare [0,30] and [5,10] → overlap found

Python Code

Copy codeclass Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        intervals.sort()
        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i-1][1]:
                return False
        return True

Complexity

• Time: O(n log n) - Dominated by sorting
• Space: O(1) or O(n) - Depending on sort implementation
• Why Best: Efficient and clean

Solution 3: Min-Heap Approach

Explanation

Use a min-heap to track meeting end times: 1. Sort: By start time (same as Solution 2) 2. Heap: Track earliest ending meeting 3. Overlap Check: If new meeting starts before earliest ends

Python Code

Copy codeimport heapq

class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        if not intervals:
            return True

        intervals.sort()
        heap = []
        heapq.heappush(heap, intervals[0][1])

        for interval in intervals[1:]:
            if interval[0] < heap[0]:
                return False
            heapq.heappop(heap)
            heapq.heappush(heap, interval[1])
        return True

Complexity

• Time: O(n log n)
• Space: O(n)
• Pros: Extendable to more complex problems
• Cons: Overkill for this problem

Edge Cases to Consider

1. Empty list: Should return true
2. Single meeting: Always possible
3. Back-to-back meetings: [1,2] and [2,3] are valid
4. Large intervals: Handle maximum constraints
5. Duplicate meetings: Exact same start/end times

Final Thoughts

• Interview Tip: Sorting solution is expected
• Key Insight: After sorting, only need to check adjacent pairs
• Follow-up: How would you find the minimum number of rooms needed?