252. Meeting Rooms (Easy)

Problem

Given an array of meeting time intervals [start, end], determine if a person could attend all meetings.

Example

• intervals = [[0,30],[5,10],[15,20]] → false
• intervals = [[7,10],[2,4]] → true

LeetCode 252 (premium) · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, check every pair

Compare every pair of intervals for overlap.

Python

def can_attend_meetings(intervals):
    n = len(intervals)                              # L1: O(1)
    for i in range(n):                              # L2: outer loop, n iterations
        for j in range(i + 1, n):                   # L3: inner loop, up to n-1 iterations
            a, b = intervals[i], intervals[j]       # L4: O(1) unpack
            if a[0] < b[1] and b[0] < a[1]:         # L5: overlap check, O(1)
                return False
    return True

TypeScript

function canAttendMeetings(intervals: number[][]): boolean {
    const n = intervals.length;                                    // L1: O(1)
    for (let i = 0; i < n; i++) {                                 // L2: outer loop, n iterations
        for (let j = i + 1; j < n; j++) {                        // L3: inner loop, up to n-1 iterations
            const a = intervals[i], b = intervals[j];             // L4: O(1) unpack
            if (a[0] < b[1] && b[0] < a[1]) return false;        // L5: overlap check, O(1)
        }
    }
    return true;
}

Go

func canAttendMeetings(intervals [][]int) bool {
    n := len(intervals)                                // L1: O(1)
    for i := 0; i < n; i++ {                          // L2: outer loop, n iterations
        for j := i + 1; j < n; j++ {                  // L3: inner loop, up to n-1 iterations
            a, b := intervals[i], intervals[j]         // L4: O(1) unpack
            if a[0] < b[1] && b[0] < a[1] { return false }  // L5: overlap check, O(1)
        }
    }
    return true
}

Swift

final class Solution {
    func canAttendMeetings(_ intervals: [[Int]]) -> Bool {
        for left in 0..<intervals.count {
            for right in (left + 1)..<intervals.count {
                if max(intervals[left][0], intervals[right][0]) < min(intervals[left][1], intervals[right][1]) { return false }
            }
        }
        return true
    }
}

Where the time goes, line by line

Variables: n = len(intervals).

Line	Per-call cost	Times executed	Contribution
L1 (n)	$O(1)$	1	$O(1)$
L2 (outer loop)	$O(1)$	n	$O(n)$
L3 (inner loop)	$O(1)$	n(n-1)/2 total*	$O(n²)$ ← dominates
L4-L5 (unpack + check)	$O(1)$	up to n*(n-1)/2	$O(n²)$

Every pair of intervals is inspected once. No sorting, no extra space. The quadratic cost comes directly from iterating all C(n, 2) pairs.

Complexity

• Time: $O(n²)$, driven by L3 (the nested pair enumeration).
• Space: $O(1)$.

Approach 2: Sort by start + check adjacent (canonical)

Sort. If any meeting’s start is earlier than the previous meeting’s end, there’s a conflict.

Python

def can_attend_meetings(intervals):
    intervals.sort(key=lambda x: x[0])             # L1: O(n log n)
    for i in range(1, len(intervals)):              # L2: linear scan, n-1 iterations
        if intervals[i][0] < intervals[i - 1][1]:  # L3: adjacent overlap check, O(1)
            return False
    return True

TypeScript

function canAttendMeetings(intervals: number[][]): boolean {
    intervals.sort((a, b) => a[0] - b[0]);                       // L1: O(n log n)
    for (let i = 1; i < intervals.length; i++) {                 // L2: linear scan, n-1 iterations
        if (intervals[i][0] < intervals[i - 1][1]) return false; // L3: adjacent overlap check, O(1)
    }
    return true;
}

Go

func canAttendMeetings(intervals [][]int) bool {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]  // L1: O(n log n)
    })
    for i := 1; i < len(intervals); i++ {         // L2: linear scan, n-1 iterations
        if intervals[i][0] < intervals[i-1][1] { return false }  // L3: adjacent overlap check, O(1)
    }
    return true
}

Swift

final class Solution {
    func canAttendMeetings(_ intervals: [[Int]]) -> Bool {
        let sorted = intervals.sorted { $0[0] < $1[0] }
        if sorted.count < 2 { return true }
        for index in 1..<sorted.count where sorted[index][0] < sorted[index - 1][1] { return false }
        return true
    }
}

Where the time goes, line by line

Variables: n = len(intervals).

Line	Per-call cost	Times executed	Contribution
L1 (sort)	$O(n log n)$	1	$O(n log n)$ ← dominates
L2 (loop)	$O(1)$	n-1	$O(n)$
L3 (overlap check)	$O(1)$	up to n-1	$O(n)$

Once sorted by start time, only adjacent pairs can overlap: if interval i and interval j (j > i+1) overlapped, interval i+1 would also overlap with one of them. So a single linear scan after sorting is sufficient. The sort is the only non-trivial cost.

Complexity

• Time: $O(n log n)$, driven by L1 (the sort).
• Space: $O(1)$ extra (sort is in-place for Python lists; the input is mutated).

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Sweep line on events

Decompose into +1 (start) and -1 (end) events; sort by time with -1 before +1 on ties; running sum must stay ≤ 1.

Python

def can_attend_meetings(intervals):
    events = []                                        # L1: O(1)
    for s, e in intervals:                             # L2: build events, O(n)
        events.append((s, 1))                          # L3: start event
        events.append((e, -1))                         # L4: end event
    events.sort(key=lambda x: (x[0], x[1]))            # L5: sort 2n events, O(n log n)
    cur = 0                                            # L6: O(1)
    for _, delta in events:                            # L7: scan events, 2n iterations
        cur += delta                                   # L8: O(1) update
        if cur > 1:                                    # L9: overlap if 2 active at once
            return False
    return True

TypeScript

function canAttendMeetings(intervals: number[][]): boolean {
    const events: [number, number][] = [];             // L1: O(1)
    for (const [s, e] of intervals) {                  // L2: build events, O(n)
        events.push([s, 1]);                           // L3: start event
        events.push([e, -1]);                          // L4: end event
    }
    events.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);  // L5: sort 2n events, O(n log n)
    let cur = 0;                                       // L6: O(1)
    for (const [, delta] of events) {                 // L7: scan events, 2n iterations
        cur += delta;                                  // L8: O(1) update
        if (cur > 1) return false;                     // L9: overlap if 2 active at once
    }
    return true;
}

Go

func canAttendMeetings(intervals [][]int) bool {
    type event struct{ time, delta int }
    events := make([]event, 0, len(intervals)*2)  // L1: O(1)
    for _, iv := range intervals {                 // L2: build events, O(n)
        events = append(events, event{iv[0], 1})  // L3: start event
        events = append(events, event{iv[1], -1}) // L4: end event
    }
    sort.Slice(events, func(i, j int) bool {       // L5: sort 2n events, O(n log n)
        if events[i].time != events[j].time { return events[i].time < events[j].time }
        return events[i].delta < events[j].delta
    })
    cur := 0                                       // L6: O(1)
    for _, e := range events {                     // L7: scan events, 2n iterations
        cur += e.delta                             // L8: O(1) update
        if cur > 1 { return false }                // L9: overlap if 2 active at once
    }
    return true
}

Swift

final class Solution {
    func canAttendMeetings(_ intervals: [[Int]]) -> Bool {
        var events: [(time: Int, delta: Int)] = []
        for interval in intervals { events.append((interval[0], 1)); events.append((interval[1], -1)) }
        events.sort { $0.time == $1.time ? $0.delta < $1.delta : $0.time < $1.time }
        var active = 0
        for event in events { active += event.delta; if active > 1 { return false } }
        return true
    }
}

Where the time goes, line by line

Variables: n = len(intervals).

Line	Per-call cost	Times executed	Contribution
L2-L4 (build events)	$O(1)$ per interval	n	$O(n)$
L5 (sort)	$O(n log n)$	1	$O(n log n)$ ← dominates
L7-L9 (scan)	$O(1)$ per event	2n	$O(n)$

The events list has 2n entries (one start, one end per interval). Sorting 2n items is still $O(n log n)$. The tie-breaking (time, delta) sort puts -1 (end) before +1 (start) at the same time, which correctly handles back-to-back meetings that share an endpoint as non-overlapping.

Complexity

• Time: $O(n log n)$, driven by L5 (sorting 2n events).
• Space: $O(n)$ for the events list.

Useful when the next problem (Meeting Rooms II) extends the counting.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Every pair	$O(n²)$	$O(1)$
Sort + adjacent check	$O(n log n)$	$O(1)$
Sweep-line events	$O(n log n)$	$O(n)$

Sort + adjacent check is the shortest. Sweep-line generalizes to “how many rooms at peak” (252 -> 253).

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_252.py and run.
# Uses the canonical implementation (Approach 2: sort + adjacent check).

def can_attend_meetings(intervals):
    intervals.sort(key=lambda x: x[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False
    return True

def _run_tests():
    # Example: overlapping meetings
    assert can_attend_meetings([[0,30],[5,10],[15,20]]) == False
    # Example: no overlap
    assert can_attend_meetings([[7,10],[2,4]]) == True
    # Edge: empty list
    assert can_attend_meetings([]) == True
    # Edge: single meeting
    assert can_attend_meetings([[1,5]]) == True
    # Back-to-back: end == start is not an overlap
    assert can_attend_meetings([[1,5],[5,10]]) == True
    # Exactly overlapping by 1 unit
    assert can_attend_meetings([[1,6],[5,10]]) == False
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function canAttendMeetings(intervals: number[][]): boolean {
    intervals.sort((a, b) => a[0] - b[0]);
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < intervals[i - 1][1]) return false;
    }
    return true;
}

console.assert(canAttendMeetings([[0,30],[5,10],[15,20]]) === false);
console.assert(canAttendMeetings([[7,10],[2,4]]) === true);
console.assert(canAttendMeetings([]) === true);
console.assert(canAttendMeetings([[1,5]]) === true);
console.assert(canAttendMeetings([[1,5],[5,10]]) === true);
console.assert(canAttendMeetings([[1,6],[5,10]]) === false);
console.log("all tests pass");

Related data structures

• Arrays, sort + linear scan

Related concepts

• Merge Intervals, the sorted boundary scan for combining or rejecting overlapping ranges.
• Intervals, the range representation behind starts, ends, overlap, and coverage.