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.
For example, Given [[0, 30],[5, 10],[15, 20]], return 2.
O(n log n) Heap solution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ public class Solution { public int minMeetingRooms (Interval[] intervals) { if (intervals == null || intervals.length == 0 ) { return 0 ; } Arrays.sort(intervals, (a,b) -> (a.start - b.start)); PriorityQueue<Interval> pq = new PriorityQueue<Interval>((a,b) -> (a.end - b.end)); pq.offer(intervals[0 ]); for (int i = 1 ; i < intervals.length; i++) { Interval prev = pq.poll(); Interval cur = intervals[i]; if (cur.start >= prev.end) { prev.end = cur.end; } else { pq.offer(cur); } pq.offer(prev); } return pq.size(); } }