Golang solution (22ms)


  • 0

    Solution #1: using a list of end points

    func minMeetingRooms(intervals []Interval) int {
        endPoints := EndPoints{}
        for _, interval := range intervals {
            endPoints = append(endPoints, EndPoint{time: interval.Start, isStart: true})
            endPoints = append(endPoints, EndPoint{time: interval.End, isStart: false})
        }
        sort.Sort(endPoints)
        result, roomCount := 0, 0
        for _, endPoint := range endPoints {
            if endPoint.isStart {
                roomCount++
                result = max(result, roomCount)
            } else {
                roomCount--
            }
        }
        return result
    }
    
    func max(x, y int) int {if x > y {return x}; return y}
    
    // Use sort.Slice() with Go version >= 1.8 to avoid implementing the sort interface
    type EndPoint struct {time int; isStart bool}
    type EndPoints []EndPoint
    func (e EndPoints) Len() int {return len(e)}
    func (e EndPoints) Swap(i, j int) {e[i], e[j] = e[j], e[i]}
    func (e EndPoints) Less(i, j int) bool {
        if e[i].time == e[j].time {return !e[i].isStart && e[j].isStart}
        return e[i].time < e[j].time
    }
    

    Solution #2: using a min heap

    func minMeetingRooms(intervals []Interval) int {
        if len(intervals) <= 1 {return len(intervals)}
        sort.Sort(Intervals(intervals))
        minHeap := &Heap{}
        heap.Push(minHeap, intervals[0].End)
        for i := 1; i < len(intervals); i++ {
            if intervals[i].Start >= minHeap.Top() {
                heap.Pop(minHeap)
            }
            heap.Push(minHeap, intervals[i].End)
        }
        return minHeap.Len()
    }
    
    // Use sort.Slice() with Go version >= 1.8 to avoid implementing the sort interface
    type Intervals []Interval
    func (m Intervals) Len() int {return len(m)}
    func (m Intervals) Swap(i, j int) {m[i], m[j] = m[j], m[i]}
    func (m Intervals) Less(i, j int) bool {return m[i].Start < m[j].Start}
    
    type Heap []int
    func (h Heap) Len() int {return len(h)}
    func (h Heap) Swap(i, j int) {h[i], h[j] = h[j], h[i]}
    func (h Heap) Less(i, j int) bool {return h[i] < h[j]}
    func (h Heap) Top() int {return h[0]}
    func (h *Heap) Push(x interface{}) {*h = append(*h, x.(int))}
    func (h *Heap) Pop() interface{} {
        x := (*h)[len(*h)-1]
        *h = (*h)[:len(*h)-1]
        return x
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.