LeetCode 252 - Meeting Rooms

Difficulty: 🟢 Easy
Topics: Array, Sorting

Solution

Problem Understanding

The problem provides a list of meeting intervals, where each interval is represented as [start, end]. Each pair describes the start time and end time of a meeting. The task is to determine whether a single person can attend every meeting without any scheduling conflicts.

In simpler terms, we need to check whether any two meetings overlap in time. If even one overlap exists, then the person cannot attend all meetings, and the function should return false. If no meetings overlap, then the person can attend all of them, and the function should return true.

For example, consider the intervals [[0,30],[5,10],[15,20]]. The first meeting runs from time 0 to 30, while the second meeting starts at 5. Since 5 occurs before 30, the meetings overlap, making it impossible to attend both. Therefore, the answer is false.

The constraints provide important information about the scale of the input:

The number of intervals can be as large as 10^4
Meeting times are integers
Each interval is guaranteed to have start < end

The input size is large enough that inefficient quadratic solutions may become expensive, especially in worst case scenarios. This strongly suggests that sorting will likely be useful, since sorting allows overlapping intervals to become adjacent and easy to compare efficiently.

Several edge cases are important to consider:

An empty list of meetings should return true, because there are no conflicts.
A single meeting should also return true.
Meetings that touch but do not overlap, such as [1,5] and [5,10], are valid because the first meeting ends exactly when the second begins.
Multiple overlapping meetings must be detected correctly even if they are not initially adjacent in the input order.
The intervals may arrive unsorted, so relying on the original order would be incorrect.

Approaches

Brute Force Approach

The most straightforward solution is to compare every meeting with every other meeting. For each pair of intervals, we check whether their time ranges overlap.

Two meetings overlap if:

The first meeting starts before the second meeting ends
The second meeting starts before the first meeting ends

If any overlap is found, we immediately return false. If all pairs are checked without finding a conflict, we return true.

This approach works because it explicitly verifies every possible pair of meetings. However, it is inefficient because it performs redundant comparisons. With n meetings, there are approximately n^2 pairs to check.

Given that n can be as large as 10^4, this quadratic solution may perform up to 100 million comparisons in the worst case, which is unnecessarily expensive.

Optimal Approach

The key observation is that overlapping meetings become much easier to detect after sorting the intervals by their start times.

Once the intervals are sorted:

Any overlapping meeting must appear next to another overlapping meeting
We only need to compare each interval with the previous one

This works because sorting guarantees chronological order. If the current meeting starts before the previous meeting ends, then the meetings overlap.

This reduces the problem from checking all possible pairs to checking only adjacent intervals after sorting.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Compare every pair of intervals
Optimal	O(n log n)	O(1) or O(log n) depending on sorting implementation	Sort intervals, then scan once for overlaps

Algorithm Walkthrough

Sort the intervals by their start times.

Sorting is the most important step because it places meetings in chronological order. Once sorted, any overlap must occur between neighboring meetings. 2. Iterate through the sorted intervals starting from the second meeting.

We compare each meeting with the one immediately before it. Since the meetings are ordered by start time, this is sufficient to detect all conflicts. 3. For each interval, compare its start time with the previous interval's end time.

If:

$currentStart < previousEnd$

then the meetings overlap. 4. If an overlap is found, immediately return False.

There is no need to continue checking once a conflict exists. 5. If the loop completes without detecting overlaps, return True.

This means every meeting starts after or exactly when the previous meeting ends.

Why it works

After sorting, meetings are ordered by increasing start time. If any overlap exists anywhere in the schedule, then at least one meeting must begin before the previous meeting ends. Since all earlier meetings already end no later than the immediately previous meeting, checking adjacent intervals is sufficient to detect every possible conflict.

Python Solution

from typing import List

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        # Sort meetings by start time
        intervals.sort(key=lambda interval: interval[0])

        # Check adjacent meetings for overlap
        for i in range(1, len(intervals)):
            previous_end = intervals[i - 1][1]
            current_start = intervals[i][0]

            if current_start < previous_end:
                return False

        return True

The implementation begins by sorting the intervals using their start times. Python's built in sorting is efficient and runs in O(n log n) time.

After sorting, the loop starts at index 1 because every comparison requires a previous interval. For each iteration:

previous_end stores the ending time of the earlier meeting
current_start stores the starting time of the current meeting

If the current meeting starts before the previous one ends, then the meetings overlap and the function immediately returns False.

If the loop completes without finding an overlap, then all meetings are compatible, so the function returns True.

Go Solution

package main

import "sort"

func canAttendMeetings(intervals [][]int) bool {
    // Sort intervals by start time
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    // Check adjacent intervals for overlap
    for i := 1; i < len(intervals); i++ {
        previousEnd := intervals[i-1][1]
        currentStart := intervals[i][0]

        if currentStart < previousEnd {
            return false
        }
    }

    return true
}

The Go implementation follows the same logic as the Python version. The primary difference is that Go uses sort.Slice with a custom comparator function to sort the intervals.

Go slices can safely represent empty input, so no special handling is required for empty or nil slices. Integer overflow is not a concern because the problem constraints stay well within Go's integer range.

Worked Examples

Example 1

Input:

[[0,30],[5,10],[15,20]]

After sorting:

[[0,30],[5,10],[15,20]]

The intervals are already sorted.

Step	Previous Interval	Current Interval	Comparison	Overlap?
1	[0,30]	[5,10]	5 < 30	Yes

Since an overlap is found immediately, the algorithm returns False.

Final result:

false

Example 2

Input:

[[7,10],[2,4]]

After sorting:

[[2,4],[7,10]]

Step	Previous Interval	Current Interval	Comparison	Overlap?
1	[2,4]	[7,10]	7 < 4	No

No overlaps are found.

Final result:

true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(log n)	Depends on the underlying sorting implementation

The dominant operation is sorting the intervals, which requires O(n log n) time. The subsequent scan through the intervals is linear.

The algorithm itself uses only a few extra variables. However, some sorting implementations use additional stack space internally. Python's sorting algorithm may use O(log n) auxiliary space for recursion and merging behavior.

Test Cases

from typing import List

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals.sort(key=lambda interval: interval[0])

        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i - 1][1]:
                return False

        return True

solution = Solution()

assert solution.canAttendMeetings([]) == True  # empty input
assert solution.canAttendMeetings([[1, 2]]) == True  # single meeting
assert solution.canAttendMeetings([[0, 30], [5, 10], [15, 20]]) == False  # overlapping meetings
assert solution.canAttendMeetings([[7, 10], [2, 4]]) == True  # non-overlapping unsorted input
assert solution.canAttendMeetings([[1, 5], [5, 10]]) == True  # touching intervals
assert solution.canAttendMeetings([[1, 4], [2, 5]]) == False  # direct overlap
assert solution.canAttendMeetings([[5, 8], [1, 3], [3, 5]]) == True  # sorted adjacency without overlap
assert solution.canAttendMeetings([[1, 10], [2, 3], [4, 5]]) == False  # large interval overlapping many
assert solution.canAttendMeetings([[0, 1], [1, 2], [2, 3], [3, 4]]) == True  # chain of valid meetings
assert solution.canAttendMeetings([[4, 8], [1, 2], [2, 6]]) == False  # overlap after sorting

Test	Why
`[]`	Validates empty input handling
`[[1,2]]`	Validates single interval case
`[[0,30],[5,10],[15,20]]`	Standard overlapping example
`[[7,10],[2,4]]`	Verifies sorting is necessary
`[[1,5],[5,10]]`	Confirms touching intervals are allowed
`[[1,4],[2,5]]`	Detects direct overlap
`[[5,8],[1,3],[3,5]]`	Confirms adjacency without overlap
`[[1,10],[2,3],[4,5]]`	Large interval overlaps multiple meetings
`[[0,1],[1,2],[2,3],[3,4]]`	Sequential non-overlapping meetings
`[[4,8],[1,2],[2,6]]`	Overlap revealed only after sorting

Edge Cases

One important edge case is an empty list of intervals. A naive implementation might assume at least one interval exists and accidentally access an invalid index. In this solution, the loop starts at index 1, so an empty input naturally skips the loop and correctly returns True.

Another important case is meetings that touch exactly at their boundaries, such as [1,5] and [5,10]. Some incorrect implementations use <= instead of < when checking overlaps, which would incorrectly mark these meetings as conflicting. The correct condition is strictly <, because starting exactly when another meeting ends is valid.

A third important edge case involves unsorted input. For example, [[7,10],[2,4]] appears conflicting if processed in the original order without sorting. The algorithm explicitly sorts intervals first, ensuring comparisons occur in chronological order and preventing false overlap detection.

A fourth subtle case occurs when one meeting completely contains another, such as [[1,10],[2,3]]. Some naive interval checks fail to handle containment correctly. The sorted adjacency approach handles this naturally because the contained meeting starts before the larger meeting ends, immediately triggering overlap detection.