How do you approach Meeting Rooms?

Comparing every pair is O(n^2). Sorting first makes one linear pass enough.

What is the time complexity of Meeting Rooms?

Time complexity: O(n log n) for the sort.. Space complexity: O(1) beyond the sort..

What are common mistakes on Meeting Rooms?

Not sorting first. Nearly every interval algorithm assumes the list is ordered by start, and skipping that step gives answers that are right on the sample and wrong everywhere else. Treating touching intervals as overlapping (or not) without checking which the problem means. Mutating the input intervals while iterating over them.

gitGood.dev

← Back to problems

Meeting Rooms

EasyAlgorithms

Description

Given an array of meeting time intervals where `intervals[i] = [start, end]`, determine whether a person could attend **all** meetings. Return `true` if no two meetings overlap, `false` otherwise. A meeting that ends exactly when another begins does **not** count as an overlap - `[1,2]` and `[2,3]` are fine.

Example 1

Input: intervals = [[0,30],[5,10],[15,20]]

Output: false

Example 2

Input: intervals = [[7,10],[2,4]]

Output: true

Example 3

Input: intervals = [[1,2],[2,3]]

Output: true

Constraints

- 0 <= intervals.length <= 10^4 - 0 <= start < end <= 10^6 - Intervals arrive in arbitrary order.

Meeting Rooms: approach, complexity and pitfalls

An easy intervals problem, graded against 6 test cases (3 of them hidden).

The pattern: Intervals

Sorting by start or end, then merging or scheduling overlapping ranges.

Reach for it when you see: Meetings, bookings, ranges, or anything with a start and an end.

More Intervalsproblems →

If you are stuck

Show the 3-step hint ladder

Comparing every pair is O(n^2). Sorting first makes one linear pass enough.
Sort by start time. Then only ADJACENT meetings can conflict - if the list is sorted and no neighbour pair overlaps, nothing overlaps.
Neighbours conflict when the next meeting starts strictly before the current one ends. Use a strict < so touching intervals stay legal.

The optimal approach

Show the approach: Sort, then check neighbours

The brute force compares all pairs, O(n^2). Sorting by start time buys a much stronger property: if any two meetings overlap at all, then some adjacent pair in sorted order overlaps. So a single pass over neighbours settles it.

For each consecutive pair, the conflict test is `next.start < current.end`. Getting the boundary right is the whole problem: with `<=` you would reject `[1,2]` and `[2,3]`, which are back-to-back rather than overlapping. Interviewers reliably probe this case, and it is worth stating your convention out loud before you write the comparison.

Sorting dominates the runtime; the scan is linear.

Time: O(n log n) for the sort.
Space: O(1) beyond the sort.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Intervals mistakes

These apply to the pattern as a whole, not just this problem.

Not sorting first. Nearly every interval algorithm assumes the list is ordered by start, and skipping that step gives answers that are right on the sample and wrong everywhere else.
Treating touching intervals as overlapping (or not) without checking which the problem means.
Mutating the input intervals while iterating over them.

← Back to problems

Meeting Rooms

EasyAlgorithms

Description

Example 1

Input: intervals = [[0,30],[5,10],[15,20]]

Output: false

Example 2

Input: intervals = [[7,10],[2,4]]

Output: true

Example 3

Input: intervals = [[1,2],[2,3]]

Output: true

Constraints

- 0 <= intervals.length <= 10^4 - 0 <= start < end <= 10^6 - Intervals arrive in arbitrary order.

Meeting Rooms: approach, complexity and pitfalls

An easy intervals problem, graded against 6 test cases (3 of them hidden).

The pattern: Intervals

Sorting by start or end, then merging or scheduling overlapping ranges.

Reach for it when you see: Meetings, bookings, ranges, or anything with a start and an end.

More Intervalsproblems →

If you are stuck

Show the 3-step hint ladder

Comparing every pair is O(n^2). Sorting first makes one linear pass enough.
Sort by start time. Then only ADJACENT meetings can conflict - if the list is sorted and no neighbour pair overlaps, nothing overlaps.
Neighbours conflict when the next meeting starts strictly before the current one ends. Use a strict < so touching intervals stay legal.

The optimal approach

Show the approach: Sort, then check neighbours

Sorting dominates the runtime; the scan is linear.

Time: O(n log n) for the sort.
Space: O(1) beyond the sort.

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Intervals mistakes

These apply to the pattern as a whole, not just this problem.

Not sorting first. Nearly every interval algorithm assumes the list is ordered by start, and skipping that step gives answers that are right on the sample and wrong everywhere else.
Treating touching intervals as overlapping (or not) without checking which the problem means.
Mutating the input intervals while iterating over them.