Leetcode - Meeting Rooms II

https://leetcode.com/problems/meeting-rooms-ii/

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (s_i < e_i), 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

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func minMeetingRooms(intervals [][]int) int {
    if len(intervals) < 2 {
        return len(intervals)
    }
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    h := &IntHeap{}
    heap.Init(h)
    heap.Push(h, intervals[0][1])
    for i := 1; i < len(intervals); i++ {
        top := (*h)[0]
        if top <= intervals[i][0] {
            heap.Pop(h)
        }
        heap.Push(h, intervals[i][1])
    }
    
    return len(*h)
}

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0 || intervals[0].length == 0) return 0;
        Arrays.sort(intervals, new CSortComparator());
        
        PriorityQueue<Integer> pq = new PriorityQueue();
        pq.add(intervals[0][1]);
        for (int i = 1; i < intervals.length; i++) {
            if ((int)pq.peek() <= intervals[i][0]) {
                pq.poll();
            }
            pq.add(intervals[i][1]);
        }
        return pq.size();
    }
    class CSortComparator implements Comparator<int[]> {
        @Override 
        public int compare(int[] arr1, int[] arr2) {
            if (arr1[0] > arr2[0]) return 1;
            if (arr1[0] == arr2[0]) return 0;
            return -1;
        }
    }
}

1. Sort intervals according to start time

2. Push each end time into min heap

3. Iterate intervals and see whether the top of heap is before current start time. If top is before the current start time, pop the top. Add current end time into the heap

4. After loop, count the length of heap, it's the count of room

• 相关文章
• 全局相关文章