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. // Sort the intervals by start time
  15. Arrays.sort(intervals, new Comparator<Interval>() {
  16. public int compare(Interval a, Interval b) { return a.start - b.start; }
  17. });
  18. // Use a min heap to track the minimum end time of merged intervals
  19. PriorityQueue<Interval> heap = new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>() {
  20. public int compare(Interval a, Interval b) { return a.end - b.end; }
  21. });
  22. heap.offer(intervals[0]);
  23. for (int i = 1; i < intervals.length; i++) {
  24. Interval interval = heap.poll();
  25. if (intervals[i].start >= interval.end) {
  26. interval.end = intervals[i].end;
  27. } else {
  28. heap.offer(intervals[i]);
  29. }
  30. heap.offer(interval);
  31. }
  32. return heap.size();
  33. }
  34. }