Leetcode - Maximal Rectangle
Leetcode - Summary Ranges

Leetcode - Meeting Rooms II

violet posted @ Mar 30, 2020 12:25:34 PM in 算法 with tags Algorithm array Golang Java , 326 阅读

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

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

 

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

 

NCVT MIS Result 说:
Aug 01, 2022 04:50:46 PM

NCVT stands for National Council for Vocational Training, an advisory body set up by Government of India. This council established with responsibilities of prescribing curriculum and standards for craftsmen training and bringing notice to the Government of India. NCVT stands for National Council for Vocational Training, an advisory body set up by Government of India. NCVT MIS Result This council established with responsibilities of prescribing curriculum and standards for craftsmen training and bringing notice to the Government of India. The NCVT runs under skill development and entrepreneurship by Government of India. The curriculum is specific to various pieces of training like national trade, craftsmen and respective certificates issued by the Government.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter