LeetCode Solution 252 - Meeting Rooms

Problem Statement

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

Constraints:

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti < endi <= 10^6

Optimal Approach

The key to solving this problem is checking if any two meetings overlap. The most efficient way to do this is:

1. Sort the intervals by start time.
2. Check for overlap by ensuring that no start[i] < end[i-1].

LeetCode-Compatible C++ Solution (Sorting Approach)

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
};

Step-by-Step Explanation of Code

1. Sort the intervals based on start time.
2. Iterate through the sorted intervals:
   • If intervals[i][0] < intervals[i-1][1], return false (overlapping meetings).
3. If no overlaps exist, return true.

Dry Run / Execution Steps

Example Input:

intervals = {{0,30}, {5,10}, {15,20}}

Execution Steps:

1. Sort intervals → {{0,30}, {5,10}, {15,20}}.
2. Compare {5,10} with {0,30} → Overlaps → Return false.

Example Input:

intervals = {{7,10}, {2,4}}

Execution Steps:

1. Sort intervals → {{2,4}, {7,10}}.
2. No overlaps found → Return true.

Alternative Approaches

1. Brute Force (Check all pairs)

• Compare every pair of meetings for overlap.
• Time Complexity: O(N^2)
• Space Complexity: O(1)
• Why not? Too slow for large N.

2. Using Min-Heap (Priority Queue)

• Store meeting end times in a min-heap and check for conflicts.
• Time Complexity: O(N log N)
• Space Complexity: O(N)
• Why not? Extra space is used unnecessarily.

Why Sorting is Best?

Approach	Time Complexity	Space Complexity	Feasibility
Brute Force	O(N^2)	O(1)	❌ Infeasible
Min-Heap	O(N log N)	O(N)	❌ Extra space
Sorting	O(N log N)	O(1)	✅ Best Choice

Sorting is optimal because it allows us to detect overlaps efficiently with O(N log N) time and O(1) space.

Conclusion

The Sorting Approach is the most efficient method to solve this problem as it provides a clean way to detect overlapping meetings without additional space overhead.

Similar Problems for Practice

• Meeting Rooms II (LeetCode 253)
• Non-overlapping Intervals (LeetCode 435)
• Minimum Number of Arrows to Burst Balloons (LeetCode 452)