Meeting Rooms (LC 252)

Pattern: Merge Intervals
Difficulty: Easy
Key Concept: After sorting by start time, a person can attend all meetings iff every meeting starts on or after the previous meeting’s end (no overlap).

Problem Statement

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], determine if one person can attend all meetings. That is true only if no two intervals overlap (touching at a point is usually considered non-overlapping for “end then next start”: [0,10] and [10,15] are OK if the problem treats end as exclusive—but on LeetCode 252, equal boundary typically means no overlap if we use prevEnd <= curStart; the classic check is curStart < prevEnd for overlap).

Input: int[][] intervals — each row is [start, end].
Output: boolean — true if all meetings can be attended, false if any overlap exists.

Overlap rule (standard for LC 252): Two intervals [a,b] and [c,d] overlap if c < b after sorting so the earlier-starting meeting is first (equivalently, second starts before first ends).

---

1. Algorithm & Pseudocode

Brute force

1. For each pair (i, j) with i < j, check if intervals i and j overlap.
2. Two intervals overlap if max(start_i, start_j) < min(end_i, end_j) (or use case analysis).
3. If any pair overlaps, return false; else true.

Optimal

1. If intervals is empty, return true.
2. Sort intervals by start time ascending (intervals[i][0]).
3. Track prevEnd = intervals[0][1].
4. For k from 1 to n-1: if intervals[k][0] < prevEnd, return false; else prevEnd = intervals[k][1].
5. Return true.

---

2. Step-by-Step Analysis (Beginner-Friendly)

• Why sort by start? Once meetings are in time order, the only interval that could overlap the “current chain” is the next one in the list—you never need to compare non-adjacent pairs after sorting (if the next doesn’t overlap the previous, earlier meetings end even sooner, so no hidden overlap).
• Why curStart < prevEnd? If the next meeting starts before the previous one ends, both are active at once → impossible for one person.
• Why not <=? If curStart == prevEnd, the first ends exactly when the second starts—usually allowed (back-to-back). So strict < detects real overlap.
• Brute force intuition: Checking every pair is correct but redundant once order is known; sorting reduces the problem to a single linear scan.

---

3. The Dry Run

Input: intervals = [[0,30],[5,10],[15,20]]
After sort by start (already sorted): same order.

Step	k	prevEnd (before)	Current interval	Check start < prevEnd?	Action	prevEnd (after)
Init	—	—	—	—	Set prevEnd = 30 (from [0,30])	30
1	1	30	[5,10]	5 < 30 → true	Return false	—

Output: false (meetings [0,30] and [5,10] overlap).

Note: If we had [[7,10],[2,6]], sort gives [[2,6],[7,10]]; 7 < 6 is false; answer true.

---

4. Java Solution

Brute Force

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        int n = intervals.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int a0 = intervals[i][0], a1 = intervals[i][1];
                int b0 = intervals[j][0], b1 = intervals[j][1];
                if (Math.max(a0, b0) < Math.min(a1, b1)) {
                    return false;
                }
            }
        }
        return true;
    }
}

Time: O(n²). Space: O(1).

Optimal

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return true;
        }
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        // Alternative: Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        int prevEnd = intervals[0][1];
        for (int k = 1; k < intervals.length; k++) {
            if (intervals[k][0] < prevEnd) {
                return false;
            }
            prevEnd = intervals[k][1];
        }
        return true;
    }
}

Time: O(n log n) (sort). Space: O(1) or O(log n) stack for sort, depending on JVM.

---

5. The “Java vs. Others” Edge

• Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])): Lambda comparator is idiomatic on Java 8+; Integer.compare avoids overflow from a[0] - b[0].
• Comparator.comparingInt(a -> a[0]): Often cleaner and reads as “sort by first column”—good for interviews.
• C++: You’d use sort(intervals.begin(), intervals.end(), cmp) with a lambda or operator< on a struct—same idea, more boilerplate for raw vector<vector<int>>.
• Python: intervals.sort(key=lambda x: x[0]) is very short; Java is more verbose but explicit about types.
• Warm-up: LC 252 is the natural lead-in to Meeting Rooms II (LC 253), where you count concurrent meetings or rooms.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n²)	O(1)	Check every pair for overlap.
Optimal	O(n log n)	O(1) aux.	Sort by start, one pass comparing adjacent.