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.
For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.
Solution:
1. /*
2. * Definition for an interval.
3. * public class Interval {
4. * int start;
5. * int end;
6. * Interval() { start = 0; end = 0; }
7. * Interval(int s, int e) { start = s; end = e; }
8. * }
9. /
10. public class Solution {
11. public int minMeetingRooms(Interval[] intervals) {
12. if (intervals == null || intervals.length == 0)
13. return 0;
14. 15. // Sort the intervals by start time
16. Arrays.sort(intervals, new Comparator() {
17. public int compare(Interval a, Interval b) { return a.start - b.start; }
18. });
19. 20. // Use a min heap to track the minimum end time of merged intervals
21. PriorityQueue heap = new PriorityQueue(intervals.length, new Comparator() {
22. public int compare(Interval a, Interval b) { return a.end - b.end; }
23. });
24. 25. heap.offer(intervals[0]);
26. 27. for (int i = 1; i < intervals.length; i++) {
28. Interval interval = heap.poll();
29. 30. if (intervals[i].start >= interval.end) {
31. interval.end = intervals[i].end;
32. } else {
33. heap.offer(intervals[i]);
34. }
35. 36. heap.offer(interval);
37. }
38. 39. return heap.size();
40. }
41. }