Meeting Rooms II
给一个interval的array是conference的start time和end time, 求几个room能重下这些conference.
这个题是看答案1写的, 主要利用的思维就是, 用一个PriorityQueue存end time, 因为算法主要的难点就是找到当前的interval和哪个room的interval重叠, 如果通过merge interval来判断, 那么code就会特别长, 这时需要用这个pq来存end time, 换一种思维, 如果这个end time比start time靠后(大), 那么就是当前的interval肯定发生在end time之前, 那么便需要一个新的房间. if(!pq.isEmpty() && pq.peek()[1] <= i[0]) 这个代码可以通过判断pq最靠前的end time是否小于或者等于(正好结束)当前的starttime, 如果yes, 那么说明有某个(这里不需要知道那个)room的endtime已经结束, 可以给新的conference. pq.poll()便是把老时间踢出, 然后再放入新的时间.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public int minMeetingRooms(int[][] intervals) { Arrays.sort(intervals, (a, b) -> (a[0] - b[0])); PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] - b[1])); for(int[] i : intervals) { if(!pq.isEmpty() && pq.peek()[1] <= i[0]) pq.poll(); pq.add(i); } return pq.size(); } } |