Meeting Rooms II: Event Sweep

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
    // Ties: process ends before starts (half-open intervals)

    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.