Problem overview
The method meetingRooms(intervals) receives meetings as a slice of [start, end] pairs and returns the minimum number of rooms needed so that every meeting gets a room for its whole duration. Meetings that touch, where one ends at the moment another begins, don't overlap and can share a room. Each end is greater than its start.
For [[5, 10], [0, 30], [15, 20]] the answer is 2. The meeting from 0 to 30 runs the whole time and needs its own room. The other two, 5 to 10 and 15 to 20, don't overlap each other, so they can share a second room. The statement asks for O(n log n) time and O(n) extra space.
Approach: turn meetings into events and sweep through time
The number of rooms needed is the largest number of meetings that are in progress at the same moment. Comparing every pair of meetings to find that peak would take O(n²) time. A sweep does it with a sort.
Split each meeting into two events: a start at time s, which adds a meeting to the count, and an end at time e, which removes one. Sort all events by time and walk through them in order, keeping a running count of meetings in progress. The highest value the count reaches is the answer.
Ties need care. If one meeting ends at time 10 and another starts at 10, the two events share a time. Processing the end first frees the room before the start asks for one, so the touching meetings share a room, as the statement requires. If the start were processed first, the count would briefly show 2 and the answer would be too high. The events are therefore stored as pairs [time, type], with type 1 for a start and -1 for an end. Comparing the type when the times are equal puts -1 before 1.
For the example, the sorted events and the running count are:
[0 1] count 1
[5 1] count 2
[10 -1] count 1
[15 1] count 2
[20 -1] count 1
[30 -1] count 0
The largest count is 2, which is the answer.
Step by step
- Create the events slice. Declare
eventsas a[][]intwithmake, length 0 and capacitylen(intervals)*2. Every meeting adds exactly two events, soappendnever needs to grow the storage. - Loop over the meetings with
for _, interval := range intervals. The blank identifier discards the index, which would otherwise be an unused variable. - Append the start event
[]int{interval[0], 1}. Assign the result ofappendback toevents. - Append the end event
[]int{interval[1], -1}the same way. - Sort the events with
sort.Slice. The comparison function returns true when the event atimust come first: if the times are equal, the smaller type wins; otherwise the earlier time wins. - Prepare the counters. Declare
answerandnoOfMeetings, both 0, in one statement. The second is the number of meetings in progress, and the first is the largest value seen. - Walk the sorted events with another
rangeloop that discards the index. - Update the count by adding the event's type:
noOfMeetings += event[1]. The values 1 and -1 turn "add or remove a meeting" into one addition. - Track the peak with
answer = max(answer, noOfMeetings). - Return
answer.
The solution in Go
type Solution struct {}
func (this Solution) meetingRooms(intervals [][]int) int {
events := make([][]int, 0, len(intervals)*2)
for _, interval := range intervals {
events = append(events, []int{interval[0], 1})
events = append(events, []int{interval[1], -1})
}
sort.Slice(events, func(i, j int) bool {
if events[i][0] == events[j][0] {
return events[i][1] < events[j][1]
}
return events[i][0] < events[j][0]
})
answer, noOfMeetings := 0, 0
for _, event := range events {
noOfMeetings += event[1]
answer = max(answer, noOfMeetings)
}
return answer
}
Go details worth a closer look:
make([][]int, 0, n)takes the element type, the starting length and an optional capacity. With length 0 the slice starts empty, and the reserved capacity means the appends fill existing storage instead of reallocating. Without the capacity the code would still be correct, just slower.appendreturns a slice. It may allocate a new array, so the result must be assigned back. Callingappend(events, x)and ignoring the result would leaveeventsunchanged.[]int{interval[0], 1}is a slice literal. Each event is its own two-element slice, which is whyeventshas type[][]int.- The blank identifier
_is needed because Go rejects unused variables.rangeover a slice yields an index and an element, and here only the element is wanted. sort.Sliceneeds thesortpackage imported and sorts in place. The function receives indices intoevents, not the events. It isn't a stable sort, but two events with the same time and type are interchangeable, so the order among them doesn't matter.- Built-in
maxis available from Go 1.21 and needs no import.
Complexity
There are 2n events. Sorting them takes O(n log n) time and the sweep is linear, so the total is O(n log n). The events slice stores 2n small slices, so the extra space is O(n), as the statement allows. The function does not change intervals.
Edge cases and common mistakes
- Touching meetings. For
[[1, 2], [2, 3]]the sorted events are[1 1],[2 -1],[2 1],[3 -1], so the count never passes 1 and the answer is 1. Sorting by time alone, with no tie-break, could put the start first and report 2. - One meeting. The answer is 1.
- Fully nested or identical meetings. Three meetings with the same start and end give 3, because their start events all come before their end events.
- No meetings. The loops do nothing and the answer is 0.
- Reversing the tie-break. Using
>on the types puts starts before ends and overcounts touching meetings. - Forgetting to assign
append's result, which loses the events.
Testing
Try [[5, 10], [0, 30], [15, 20]] (answer 2), [[1, 2], [2, 3]] (answer 1) and [[1, 4], [2, 5], [3, 6]] (answer 3, since all three are running at time 3).