252. Meeting Rooms — DSA Atlas

252

EasyIntervals and Sweep LineSorting + linear scanSort by start, check adjacent overlap

Meeting Rooms

Given an array of meeting time intervals where intervals[i] = [start_i, end_i], determine whether a person could attend all meetings, i.e. return true if no two meetings overlap.

Open official problem prompt ↗

In plain English

Decide whether a single person can attend every meeting, which is true exactly when no two meetings overlap in time.

Picture it like this

Checking a personal calendar for double-booking: line up appointments by start time and see if any begins before the one before it wraps up.

Example

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false
Why: [0,30] and [5,10] overlap (5 < 30), so the person cannot attend both.

Constraints

1 <= intervals.length <= 10^40 <= start_i < end_i <= 10^6

Pattern lesson

See the pattern, then code

Sort by start, check adjacent overlap

↗

Intervals and Sweep Line

Meetings, schedules, overlapping ranges, resource allocation, or timeline events.. After sorting by start, meetings are in chronological order, so an overlap can only occur between neighbors; if any meeting starts before the previous one ends, attendance is impossible.

New words, made simpleKnow these before the algorithm

Overlap: Two meetings overlap when one starts strictly before the other ends.
Adjacent check: Comparing each interval only with the one immediately before it after sorting.
Chronological order: The start-sorted arrangement that localizes all possible conflicts to neighbors.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

All-pairs comparison

Correct but quadratic and unnecessary.

Compare every pair of meetings for overlap.

Time O(n^2)Space O(1)

Best choiceSort then neighbor check

Sorting confines conflicts to adjacent pairs, so one pass decides it.

Sort by start and verify each meeting begins at or after the previous one ends.

Time O(n log n)Space O(1)

The rule we keep true

Invariant

For every index examined so far, all meetings up to that point are mutually non-overlapping; the first violated neighbor comparison proves the answer is false.

Why this is correct

Reasoning

If meetings are sorted by start and some pair overlaps, then in particular the earlier-ending of an overlapping pair is adjacent to a meeting it conflicts with; checking each meeting against only its predecessor therefore catches any overlap that exists.

The algorithm in three movesSay these aloud before coding

1Sort meetings by start time

sorted: [0,30],[5,10],[15,20]

2Scan adjacent pairs from index 1

5 < 30 -> overlap detected

3If a meeting's start is less than the previous meeting's end, return false

return false

4If no such conflict is found, return true

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[0,30]0

[5,10]1

[15,20]2

1 · Read[[0,30],[5,10],[15,20]]

2 · AskOrder by start?

3 · Update state-

4 · Resultunchanged

Key takeaway

Meeting [5,10] starts at 5 while [0,30] runs until 30 — an overlap.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3Sort by start
Puts meetings in chronological order so conflicts are between neighbors only.
2
Lines 4-6Neighbor overlap test
start < previous end means the two meetings overlap, so attendance is impossible.
3
Lines 7No conflict found
Completing the loop without a violation means all meetings are attendable.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single meeting is always attendable (true)
Meetings touching at endpoints like [1,5] and [5,8] do NOT overlap (true)
Identical meetings overlap (false)
Already-sorted vs unsorted input

Common beginner mistakes

Using <= instead of < and wrongly rejecting back-to-back meetings that merely touch
Forgetting to sort, so the neighbor check misses conflicts
Comparing wrong fields (start vs start instead of start vs previous end)

Check your understanding

Why is comparing each meeting only to its immediate predecessor sufficient after sorting?

Meeting Rooms

Meeting Rooms

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Intervals and Sweep Line