133.Meeting Rooms

EasyBlind 75Intervals · 4/6

Problem

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], determine whether one person could attend all of the meetings — that is, whether no two meetings overlap.

A meeting ending at time t and another starting at time t do not conflict: [5,10] and [10,15] are fine.

Examples

Input:  intervals = [[0,30],[5,10],[15,20]]
Output: false
Explanation: [0,30] overlaps both [5,10] and [15,20].

Input:  intervals = [[7,10],[2,4]]
Output: true
Explanation: Sorted: [2,4] then [7,10] — no overlap.

Input:  intervals = [[5,10],[10,15]]
Output: true
Explanation: The first meeting ends exactly when the second begins.

Constraints

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= start_i < end_i <= 10^6

💡 Key Insight

Once meetings are sorted by start time, a conflict can only happen between neighbours: if meeting i does not overlap meeting i + 1, it cannot overlap any later meeting either, because those start even later. So sort and check intervals[i][0] < intervals[i - 1][1] for each adjacent pair.

Brute Force (Check Every Pair)

TimeO(n²)SpaceO(1).

Intuition

Two meetings a and b overlap exactly when each starts before the other ends: a[0] < b[1] && b[0] < a[1]. Test all pairs.

Algorithm

For each i, for each j > i:
If intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1], return false.
Return true.

Visualization

[0,30] vs [5,10]:  0 < 10 and 5 < 30  -> overlap -> false

Code

java

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++) {
                // strict < so that touching meetings are allowed
                if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {
                    return false;
                }
            }
        }
        return true;
    }
}

Complexity

Time: O(n²) — every pair is compared.
Space: O(1).

Sweep Line with a TreeMap

TimeO(n log n)SpaceO(n)

Intuition

Turn each meeting into two events: +1 at its start and -1 at its end. Walking the time points in order while summing the deltas gives how many meetings are running. If that count ever exceeds 1, there is a conflict. Storing deltas per time in a TreeMap makes an end and a start at the same time cancel out, which correctly allows back-to-back meetings.

Algorithm

For each meeting: delta[start] += 1, delta[end] -= 1 in a TreeMap.
Iterate keys ascending, running += delta; if running > 1, return false.
Return true.

Visualization

[[0,30],[5,10],[15,20]]
time:     0   5   10  15  20  30
delta:   +1  +1  -1  +1  -1  -1
running:  1   2 -> conflict -> false

Code

java

import java.util.Map;
import java.util.TreeMap;

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        TreeMap<Integer, Integer> delta = new TreeMap<>();
        for (int[] m : intervals) {
            delta.merge(m[0], 1, Integer::sum);
            delta.merge(m[1], -1, Integer::sum); // same-time end and start cancel
        }
        int running = 0;
        for (Map.Entry<Integer, Integer> e : delta.entrySet()) {
            running += e.getValue();
            if (running > 1) {
                return false; // two meetings at once
            }
        }
        return true;
    }
}

Complexity

Time: O(n log n) — 2n TreeMap insertions.
Space: O(n) — the map.

Sort by StartOptimal

TimeO(n log n)SpaceO(log n)

Intuition

Sort by start. Each meeting must begin no earlier than the previous one ends. Checking adjacent pairs is enough because sorted order guarantees that a later meeting starts even later than the next one.

Algorithm

Sort intervals by start time.
For i from 1 to n - 1: if intervals[i][0] < intervals[i - 1][1], return false.
Return true.

Dry Run

flowchart LR
    A["sorted: [0,30] [5,10] [15,20]"] --> B{"5 < 30?"}
    B -->|"yes: overlap"| C["return false"]
    D["sorted: [2,4] [7,10]"] --> E{"7 < 4?"}
    E -->|"no"| F["return true"]

time:   0    5    10   15   20   25   30
[0,30]  [-----------------------------]
[5,10]       [----]
[15,20]                [----]
             ^ starts before [0,30] ends -> conflict

Code

java

import java.util.Arrays;

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false; // starts before the previous meeting ends
            }
        }
        return true;
    }
}

Complexity

Time: O(n log n) — sorting; the scan is O(n).
Space: O(log n) — sort recursion stack.

Complexity Comparison

Approach	Time	Space
Check Every Pair	O(n²)	O(1)
Sweep Line (TreeMap)	O(n log n)	O(n)
Sort by Start	O(n log n)	O(log n)

Common Pitfalls

Using <= in the overlap check — [5,10] and [10,15] must be allowed.
Comparing only with intervals[0] instead of the immediately previous meeting.
Forgetting the empty input: zero meetings can trivially all be attended (true).
In the sweep-line version, processing a start before an end at the same timestamp — merging deltas per timestamp (or ordering ends first) avoids a false conflict.