LeetCode: Meeting Rooms II

Posted on August 5, 2018July 26, 2020 by braindenny

Meeting Rooms II

Similar Problems:

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

Input: [[7,10],[2,4]]
Output: 1

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// https://code.dennyzhang.com/meeting-rooms-ii
// Basic Ideas: heap
//
//   Allocate the earlier requester
//   If all meeting rooms occupied, check whether we can release one
//   If not, add one more meeting room.
//
//   How to check which meeting room to release? min heap
//
// Complexity: Time O(n*log(n)), Space O(n)
import "sort"
import "container/heap"

// minheap
type MyHeap []int
func (h MyHeap) Len() int {
    return len(h)
}
func (h MyHeap) Less(i, j int) bool {
    return h[i]<h[j]
}

func (h MyHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *MyHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MyHeap) Pop() interface{} {
    res := (*h)[len(*h)-1]
    *h = (*h)[0:len(*h)-1]
    return res
}

func minMeetingRooms(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    res := 0
    h := &MyHeap{}
    heap.Init(h)
    for _, interval := range intervals {
        // check whether we can release one
        if h.Len()>0 && (*h)[0]<=interval[0] {
            heap.Pop(h)
        } else {
            res++
        }
        heap.Push(h, interval[1])
    }
    return res
}

// https://code.dennyzhang.com/meeting-rooms-ii
// Basic Ideas: heap
//
//   Allocate the earlier requester
//   If all meeting rooms occupied, check whether we can release one
//   If not, add one more meeting room.
//
//   How to check which meeting room to release? min heap
//
// Complexity: Time O(n*log(n)), Space O(n)
import "sort"
import "container/heap"

// minheap
type MyHeap []int
func (h MyHeap) Len() int {
    return len(h)
}
func (h MyHeap) Less(i, j int) bool {
    return h[i]<h[j]
}

func (h MyHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h *MyHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MyHeap) Pop() interface{} {
    res := (*h)[len(*h)-1]
    *h = (*h)[0:len(*h)-1]
    return res
}

func minMeetingRooms(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    res := 0
    h := &MyHeap{}
    heap.Init(h)
    for _, interval := range intervals {
        // check whether we can release one
        if h.Len()>0 {
            time := heap.Pop(h).(int)
            if time > interval[0] {
                heap.Push(h, time)
                res++
            }
        } else {
            res++
        }
        heap.Push(h, interval[1])
    }
    return res
}

Post Views: 7