Meeting Rooms - Leetcode 252 - Python
Meeting Rooms - Video Solution
Watch 10 video solutions for Meeting Rooms, a easy level problem involving Array, Sorting. This walkthrough by NeetCode has 131,755 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.
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 <= 104intervals[i].length == 20 <= starti < endi <= 106
Approach Overview
Problem Overview: You’re given an array of meeting time intervals where intervals[i] = [start, end]. The goal is simple: determine whether a single person can attend every meeting. If any two meetings overlap in time, attending all of them becomes impossible.
Approach 1: Brute Force Pair Comparison (O(n²) time, O(1) space)
The direct approach checks every pair of meetings to see if their time ranges intersect. For two intervals [s1, e1] and [s2, e2], an overlap exists if s1 < e2 and s2 < e1. Iterate through the array with two nested loops and test each pair. If any overlap is detected, return false; otherwise all meetings are compatible.
This method works but scales poorly. With n meetings you perform roughly n² comparisons, which becomes inefficient for larger inputs. It’s useful as a baseline to demonstrate understanding of interval overlap logic but rarely the preferred interview solution.
Approach 2: Sorting by Start Time (O(n log n) time, O(1) extra space)
A more efficient solution sorts the intervals by their start times using a standard sorting algorithm. After sorting, overlapping meetings must appear next to each other. Iterate once through the sorted list and compare the current meeting’s start time with the previous meeting’s end time.
If intervals[i].start < intervals[i-1].end, the meetings overlap and the person cannot attend both. If no such conflict appears during the scan, the schedule is valid. Sorting costs O(n log n), and the subsequent pass is O(n), giving a total time complexity of O(n log n). The scan itself uses constant extra memory aside from the sort implementation.
The key insight: once intervals are ordered by start time, only adjacent intervals need comparison. Any overlap will be revealed immediately during the linear scan.
This pattern appears frequently in interval problems. Sorting first simplifies reasoning and avoids expensive pairwise checks. Problems involving schedules, calendars, or ranges often combine arrays with sorting and linear sweeps.
Recommended for interviews: The sorting approach is what interviewers expect. Mention the brute force method briefly to show you understand overlap detection, then optimize by sorting and performing a single pass. That demonstrates both problem decomposition and knowledge of common interval strategies.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Small input sizes or when demonstrating basic overlap logic before optimization |
| Sorting + Linear Scan | O(n log n) | O(1) extra (depends on sort) | General case and expected interview solution for interval scheduling checks |