Meeting Rooms

LeetCode 252: Meeting Rooms Solution & Explanation

Problem Overview

TL;DR: Sort meetings by start time, then check every adjacent pair; if a meeting starts before the previous meeting ends, a conflict exists.

LeetCode 252, Meeting Rooms, asks whether one person can attend every meeting in a list. Each meeting is represented as [start, end]. Meetings that overlap cannot both be attended, while meetings where one ends exactly when another begins are compatible.

The LeetCode 252 Solution uses sorting followed by a single linear scan. After ordering meetings by their start times, only adjacent meetings need to be compared.

Brute Force Approach for Meeting Rooms

A naive solution checks every pair of meetings to determine whether they overlap.

For two intervals [startA, endA] and [startB, endB], they overlap if:

startA < endB AND startB < endA

Because meetings that touch at an endpoint do not conflict, equality is allowed. For example, [2, 5] and [5, 8] do not overlap.

Naive Pseudocode

for each meeting i:
    for each meeting j after i:
        if start[i] < end[j] and start[j] < end[i]:
            return false

return true

Complexity

If there are n meetings, the nested loops inspect up to:

n * (n - 1) / 2

pairs.

• Time complexity: O(n²)
• Space complexity: O(1) auxiliary space, ignoring the input

This approach becomes inefficient when n reaches 10^4. In the worst case, it performs close to 50 million pair checks. Although it may work for small inputs, it is not the optimal solution for interviews and can lead to a Time Limit Exceeded result in stricter environments.

Algorithm Strategy: Greedy Patterns

1. Sort all meetings by their start time.
2. Traverse the sorted meetings from left to right.
3. For every meeting after the first:
   • Compare its start time with the end time of the previous meeting.
   • If the current start is smaller, return false.
4. If the complete scan finishes without finding an overlap, return true.

The greedy decision is to process meetings in chronological order and reject the schedule as soon as the earliest detectable conflict appears. Sorting enforces the boundary that makes adjacent comparison sufficient.

Execution Flow

1. Order the intervals

   • Sort meetings by their starting time.
   • For intervals with the same start time, the default lexicographic ordering used by the C++ implementation is also valid because any equal-start overlap will still be detected.

2. Initialize the scan

   • Begin at index 1.
   • The meeting at index 0 has no earlier meeting to compare against.

3. Check adjacent meetings

   • Let previous be the meeting at index i - 1.
   • Let current be the meeting at index i.
   • If current.start < previous.end, return false.

4. Handle touching intervals

   • If current.start == previous.end, continue scanning.
   • These meetings do not overlap.

5. Finish the scan

   • If every adjacent pair is compatible, return true.

For example, with:

[[8, 11], [2, 5], [5, 8]]

sorting produces:

[[2, 5], [5, 8], [8, 11]]

The comparisons are:

5 < 5  -> false
8 < 8  -> false

No conflict is found, so the result is true.

For:

[[1, 4], [3, 6], [7, 9]]

the first comparison is:

3 < 4  -> true

The meetings overlap, so the algorithm returns false.

Proof of Correctness

After sorting, meetings are processed in nondecreasing order of start time.

Consider any meeting current at index i, where i > 0. Every meeting before current starts no later than current. Among those earlier meetings, the meeting at index i - 1 has the latest start time. If current overlaps any earlier meeting, the overlap must be represented by the boundary between a previously active meeting and current; specifically, the adjacent comparison detects whether:

current.start < previous.end

• If this condition is true, the two meetings overlap, so attending all meetings is impossible. Returning false is correct.
• If this condition is false, the current meeting starts at or after the previous meeting ends. The meetings are compatible, and the invariant remains valid for the next iteration.

If the algorithm completes without finding an overlap, every adjacent pair is compatible. Because the meetings are sorted by start time, no non-adjacent meeting can create an undetected conflict after all adjacent boundaries are valid. Therefore, all meetings can be attended, and returning true is correct.

Pattern Reuse Notes

The following problems share the same pattern/subpattern:

• LeetCode 2406: Divide Intervals Into Minimum Number of Groups
• LeetCode 57: Insert Interval
• LeetCode 56: Merge Intervals

These problems also organize intervals by their boundaries before making local decisions. LeetCode 2406 tracks concurrent intervals to determine the required number of groups, while LeetCode 57 and LeetCode 56 use sorted intervals to identify overlap and construct a valid merged arrangement.

Reference Implementation

C++ Solution for LeetCode 252

1class Solution {
2public:
3    bool canAttendMeetings(vector<vector<int>>& intervals) {
4        sort(intervals.begin(), intervals.end());
5
6        for (int i = 1; i < static_cast<int>(intervals.size()); ++i) {
7            if (intervals[i - 1][1] > intervals[i][0]) {
8                return false;
9            }
10        }
11
12        return true;
13    }
14};

The vector is sorted lexicographically, which sorts by meeting start time first. The scan returns false when the previous end is strictly greater than the current start. This preserves the rule that endpoint-touching meetings are allowed.

Java Solution for LeetCode 252

1class Solution {
2    public boolean canAttendMeetings(int[][] intervals) {
3        int[][] meetings = java.util.Arrays.copyOf(intervals, intervals.length);
4        java.util.Arrays.sort(meetings, (a, b) -> Integer.compare(a[0], b[0]));
5
6        for (int i = 1; i < meetings.length; i++) {
7            if (meetings[i][0] < meetings[i - 1][1]) {
8                return false;
9            }
10        }
11
12        return true;
13    }
14}

The Java implementation copies the outer array before sorting, preserving the original array reference structure. Meetings are explicitly sorted by their start times, and each meeting is compared with its predecessor.

Python Solution for LeetCode 252

1class Solution:
2    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
3        meetings = sorted(intervals, key=lambda interval: interval[0])
4
5        for i in range(1, len(meetings)):
6            if meetings[i][0] < meetings[i - 1][1]:
7                return False
8
9        return True

The Python implementation creates a sorted list ordered by interval start. It then performs the same adjacent comparison as the C++ and Java versions.