Merge Intervals — Meeting Rooms
↗ LeetCode: Meeting Rooms · Easy · pattern chapter →
Asked atMetaAmazonGoogleBloomberg
Given meeting time intervals, return true iff a person can attend all.
Example 1 — intervals=[[0,30],[5,10],[15,20]] → falseExample 2 — intervals=[[7,10],[2,4]] → trueExample 3 — intervals=[] → true
Constraints — 0 ≤ intervals.length ≤ 10⁴. Brute checks every pair — O(n²) = 10¹⁰ ops at n=10⁵ (TLE). Sort by start + linear scan for overlap is O(n log n) = ~10⁶ ops = <10 ms.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Every pair
O(n²). Baseline.
Approach 2 — Sort by start; adjacent overlap check
Insight. After sorting by start, only adjacent intervals can conflict. Walk once.
java
boolean canAttendMeetings(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
for (int i = 1; i < intervals.length; i++)
if (intervals[i][0] < intervals[i-1][1]) return false;
return true;
}Execution Trace
Step 1 / 15 < 30 → overlap → false
Complexity — Time O(n log n); Space O(1).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Every pair | O(n²) | O(1) | baseline |
| Sort + walk | O(n log n) | O(1) | optimum |
When to use which
- Boolean feasibility → sort + walk.
- Count rooms needed → Meeting Rooms II — heap or sweep line.
- Return conflict pairs → keep sorted; walk once collecting pairs.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems