#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/interval-trees/meeting-rooms-ii-event-sweep

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/interval-trees/meeting-rooms-ii-event-sweep

Repovive

Meeting Rooms II: Event Sweep - Interval Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Meeting Rooms II: Event Sweep

Start and end events

Treat each interval as two events: a start (+1 room) and an end (-1 room).

function minMeetingRooms(intervals)
    events := []
    for interval in intervals
        events.add((interval.start, +1))
        events.add((interval.end, -1))

    sort events by time
    // If same time, process ends before starts

    rooms := 0
    maxRooms := 0
    for (time, delta) in events
        rooms := rooms + delta
        maxRooms := max(maxRooms, rooms)

    return maxRooms

The maximum concurrent rooms at any time is the answer.

Time: $O(n \log n)$ for sorting. Space: $O(n)$ for events.