253. Meeting Rooms II -- 【M】 Google Snapchat Facebook / Heap / Greedy / Sort

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

clear explanation

https://discuss.leetcode.com/topic/20958/ac-java-solution-using-min-heap/19

clear solution

https://discuss.leetcode.com/topic/20958/ac-java-solution-using-min-heap/4

25ms 13%

public class Solution {

public int minMeetingRooms(Interval[] intervals) {

if (intervals == null || intervals.length == 0)

return 0;

int rooms = 0;

Arrays.sort(intervals, (a, b) -> (a.start - b.start)); //

PriorityQueue<Interval> pq = new PriorityQueue<>((a, b) -> (a.end - b.end));

for (int i = 0; i < intervals.length; i++) {

while (!pq.isEmpty() && intervals[i].start >= pq.peek().end)

pq.poll();

pq.offer(intervals[i]);

rooms = Math.max(rooms, pq.size());

}

return rooms;

}

}

*总结：

本质：计算使用最少的会议室，也就是有重复部分的会议数目。思路，分别按照start, end排两次，一边遍历一边比较，heap的size始终是最小的room，如果最先开始的会议小于heap里最先结束的，冲突，create room, 如果最早开始的会议，大于等于最早结束的会议，说明可以reuse这个room, 那么就poll()出heap头可以重复利用的room。size依然维持room的最小数目。

The reason for correctness is the invariant: heap size is always the minimum number of rooms we need so far. If the new event collides with everyone, then a new room must be created; if the new event does not collide with someone, then it must not collide with the earliest finish one, so greedily choose that one and re-use that room. So the invariant is maintained.