DSA Tracker

Visualize

Meeting Rooms

Sort by start, then check neighbours

time O(n log n)space O(1)

Unsorted, any pair could be the clash, which means checking all n^2 of them. Sorting by start time removes that: once the meetings are in time order, a meeting can only ever collide with the one immediately before it, because everything earlier ended even sooner. So one sweep over adjacent pairs decides it. A meeting that ends exactly when the next begins does NOT count as a clash — the test is strictly previous end > current start.

Details

Animated on: meetings = [[19,22],[4,8],[25,28],[0,3],[20,23],[13,15],[30,33],[8,11]] — can one person attend every meeting, or do two of them overlap?

Problem:Meeting RoomsEasy

Pattern:Intervals

Sort by start, then check neighbours

step 1 / 8

[19,22]
[0]
[4,8]
[1]
[25,28]
[2]
[0,3]
[3]
[20,23]
[4]
[13,15]
[5]
[30,33]
[6]
[8,11]
[7]

8 meetings arrive in booking order, not time order: [19,22], [4,8], [25,28], [0,3], [20,23], [13,15], [30,33], [8,11]. In this jumble a clash can sit anywhere, so there is nothing useful to compare yet.

Pseudocode
1FUNCTION canAttendAll(meetings)
2  SORT meetings BY START ASCENDING
3  FOR i <- 1 TO LENGTH(meetings) - 1
4    prevEnd <- END(meetings[i - 1])
5    currStart <- START(meetings[i])
6    IF prevEnd > currStart
7      RETURN false
8  RETURN true

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. 8 meetings arrive in booking order, not time order: [19,22], [4,8], [25,28], [0,3], [20,23], [13,15], [30,33], [8,11]. In this jumble a clash can sit anywhere, so there is nothing useful to compare yet.
  2. Sorted by start time: [0,3], [4,8], [8,11], [13,15], [19,22], [20,23], [25,28], [30,33]. Now every meeting begins no earlier than the one before it, so a clash can only ever be with the IMMEDIATE neighbour — one pass over adjacent pairs is enough.
  3. [0,3] is over by 3, and [4,8] only starts at 4 — a 1-unit gap, so no clash here.
  4. [4,8] finishes at exactly 8, the moment [8,11] begins. Touching is not overlapping, so this pair is fine and we move on.
  5. [8,11] is over by 11, and [13,15] only starts at 13 — a 2-unit gap, so no clash here.
  6. [13,15] is over by 15, and [19,22] only starts at 19 — a 4-unit gap, so no clash here.
  7. [19,22] is still running at 22 when [20,23] starts at 20. One person cannot be in two places, so the whole schedule fails here — no later pair can undo this.
  8. Return false: one clash is enough to sink the whole schedule, so we stop right here and never look at the 2 later meetings — [25,28], [30,33].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Meeting Rooms in the editorAll Intervals problemsBack to roadmap