Watch 10 video solutions for Meeting Rooms, a easy level problem involving Array, Sorting. This walkthrough by NeetCode has 174,315 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Overview: You receive a list of meeting intervals where each interval is [start, end]. Determine whether a single person can attend all meetings. If any two meetings overlap in time, attending all of them becomes impossible.
Approach 1: Pairwise Overlap Check (Brute Force) (O(n²) time, O(1) space)
Compare every interval with every other interval and check whether their time ranges intersect. Two meetings overlap if startA < endB and startB < endA. This requires a nested loop where each meeting is compared against the rest of the array. The approach uses constant extra memory and is straightforward to reason about. The downside is the quadratic runtime, which becomes expensive as the number of intervals grows.
Approach 2: Sort by Start Time (Optimal) (O(n log n) time, O(1) extra space)
Sort all intervals by their start times using a standard comparison sort. After sorting, iterate through the array once and compare each meeting with the previous one. If the current meeting's start time is earlier than the previous meeting's end time, an overlap exists and attending all meetings is impossible. Sorting ensures potential conflicts appear next to each other, reducing the problem to a single linear scan. This method combines array traversal with sorting and is the expected interview solution.
Approach 3: Sweep Line with Separate Start and End Arrays (O(n log n) time, O(n) space)
Extract all start times into one array and all end times into another. Sort both arrays independently. Use two pointers to simulate a sweep line through time: compare the earliest upcoming start with the earliest ending meeting. If a start occurs before the earliest end, it means a meeting begins while another is still active. That indicates an overlap. This technique resembles interval processing patterns used in scheduling problems and builds intuition for more advanced problems like meeting room counting.
Recommended for interviews: The sorting approach is what interviewers expect. It demonstrates that you recognize interval overlap patterns and can reduce comparisons by ordering the data first. Mentioning the brute force method shows you understand the basic overlap condition, but implementing the sort + single pass technique proves stronger problem‑solving instincts. Most interval problems on platforms like FleetCode eventually rely on sorting followed by a linear scan.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pairwise Overlap Check (Brute Force) | O(n²) | O(1) | Small input sizes or when demonstrating the raw overlap condition |
| Sort by Start Time | O(n log n) | O(1) extra (ignoring sort) | General case and the standard interview solution |
| Sweep Line with Start/End Arrays | O(n log n) | O(n) | Useful when extending to problems counting concurrent meetings |
