Meeting Rooms II
MediumThe problem
Each meeting is an Interval with a start time and an end time. Return the smallest number of rooms needed so that every meeting gets a room and no room hosts two meetings at once. A meeting may start at the exact moment another one ends, and can reuse that room.
- Example 1Input: intervals = [[0, 30], [5, 10], [15, 20]]Output: 2
The meeting 0 to 30 needs its own room, and the other two can share a second room.
- Example 2Input: intervals = [[7, 10], [2, 4]]Output: 1
They never overlap, so one room is enough.
- Example 3Input: intervals = [[1, 4], [2, 5], [3, 6]]Output: 3
At time 3 all three meetings are running.
- 0 ≤ len(intervals) ≤ 100,000
- start < end for every meeting
- Each example is written as [start, end]
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
The number of rooms needed is the maximum number of meetings happening at the same moment.
The idea
Sort starts and ends separately and sweep with two pointers (a start before the earliest end needs a new room), or use a min-heap of end times.
Target: O(n log n) time
Go function shape
func MinMeetingRooms(intervals []*Interval) intReference solution
Tested with go test. Try it yourself first, then compare.
// MinMeetingRooms: minimum rooms so no two overlapping meetings share one.
// Sweep line: sort starts and ends separately; a start before the next end needs a new room.
func MinMeetingRooms(intervals [][]int) int {
n := len(intervals)
starts, ends := make([]int, n), make([]int, n)
for i, iv := range intervals {
starts[i], ends[i] = iv[0], iv[1]
}
slices.Sort(starts)
slices.Sort(ends)
rooms, best, e := 0, 0, 0
for _, s := range starts {
for e < n && ends[e] <= s { // meetings that ended by s free their room
rooms--
e++
}
rooms++
best = max(best, rooms)
}
return best
}