Meeting Rooms II - https://leetcode.com/problems/meeting-rooms-ii/description/

gistfile1.txt

/**
 * 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; }
 * }
 */
class Solution {
    public int minMeetingRooms(Interval[] intervals) {
      if (intervals == null || intervals.length == 0) {
        return 0;
      }
      
      // Min heap
      PriorityQueue<Integer> allocator = 
        new PriorityQueue<Integer>(
        intervals.length, new Comparator<Integer>() {
          public int compare(Integer a, Integer b) {
            return a - b;
          }
        });
      
      // Lets sort on start time, and end if equals
      Arrays.sort(intervals, new Comparator<Interval>() {
        public int compare(Interval i1, Interval i2) {
          if (i1.start == i2.start) {
            return i1.end - i2.end;
          } else {
            return i1.start - i2.start;
          }
        }
      });
      
      
      // Add the first meeting
      allocator.add(intervals[0].end);

      // Iterate over remaining intervals
      for (int i = 1; i < intervals.length; i++) {
        
        Interval curInterval = intervals[i];
        
        // check if we could pop the meeting room on top.
        if (curInterval.start >= allocator.peek()) {
          allocator.poll();
        }

        // If a new room is to be assigned, then also we add to the heap,
        // If an old room is allocated, then also we have to add to the heap with updated end time.
        allocator.add(intervals[i].end);
      
      }
      
      return allocator.size();
    }
}

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.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
Example 2:

Input: [[7,10],[2,4]]
Output: 1