Solution URL
https://leetcode.com/submissions/detail/423841834/
代码
class Solution {
public int minMeetingRooms(int[][] intervals) {
//ans: Solution
//Time:O(NlogN) [1: for sort part to N elements, every elements sorting takes logN, thus total is NlogN
// 2: for minHeap part, it is nlogn too]
//Space:O(N)
//corner case
if(intervals.length == 0) return 0;
//sort the input according to the start time
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] a, int[] b){
return a[0] - b[0];
}
});
//initialize a priority queue(min heap)
PriorityQueue<Integer> pq = new PriorityQueue<>();
//put the end time of the first element into the queue
pq.add(intervals[0][1]);
//traverse the intervals, and compare the start time and the top element in pq
//if end time is larger, than replace the top element
//if the end time is smaller, than add into pq
for(int i = 1; i < intervals.length; i++){
if(intervals[i][0] >= pq.peek()){
pq.poll();
}
pq.add(intervals[i][1]);
}
return pq.size();
}
}
