Meeting Rooms

Difficulty: Easy | Acceptance: N/A | Paid: No Topics: Array, Sorting

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

• Examples
• Constraints
• Brute Force
• Sorting

Examples

Example 1:

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

Example 2:

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

Constraints

0 <= intervals.length <= 10⁴
intervals[i].length == 2
0 <= start_i < end_i <= 10⁶

Brute Force

Intuition Compare every meeting with every other meeting to check if any two intervals overlap.

Steps

• Iterate through each interval with index i.
• For each i, iterate through all subsequent intervals with index j.
• Check if intervals i and j overlap. The condition for overlap is start_i < end_j and start_j < end_i.
• If any overlap is found, return false.
• If the loops finish without finding an overlap, return true.

class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        n = len(intervals)
        for i in range(n):
            for j in range(i + 1, n):
                if intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1]:
                    return False
        return True

Complexity

• Time: O(N²) where N is the number of intervals.
• Space: O(1)
• Notes: Simple to implement but inefficient for large input sizes.

Sorting

Intuition If we sort the intervals by their start time, we only need to check if the current meeting starts before the previous meeting ends.

Steps

• Sort the intervals array based on the start time of each meeting.
• Iterate through the sorted array starting from the second interval.
• Compare the start time of the current interval with the end time of the previous interval.
• If intervals[i][0] < intervals[i-1][1], it means there is an overlap, so return false.
• If the loop completes, return true.

class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        intervals.sort(key=lambda x: x[0])
        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) due to the sorting step.
• Space: O(1) or O(N) depending on the sorting algorithm’s implementation.
• Notes: This is the most efficient approach for this problem.