Meeting Room Partitioning (Go)
Topics: scheduling, intervals, sweep line, greedy
Problem
Given a set of meetings as half-open time ranges [Start, End), find the minimum number of rooms
needed so no two meetings in the same room overlap. That number equals the maximum number of
meetings happening at the same instant.
type Interval struct { Start, End int } // half-open [Start, End)
func MinRooms(meetings []Interval) int
- Return the peak count of simultaneously-running meetings.
- Intervals are half-open: a meeting ending at
t and one starting at t do not overlap and
may share a room.
- Input may be unsorted and must not be mutated.
[0,30) [5,10) [15,20) → 2
[1,5) [2,6) [3,7) → 3
[1,2) [2,3) → 1 (touching, not overlapping)
The clean trick is a sweep: sort all start times and all end times separately, then walk them
together. Each start claims a room, each end releases one; the high-water mark of claimed rooms is
the answer. Process an end before a start at the same time so touching meetings share a room.
Sign in to submit your solution.