Meeting Rooms II

LintCode Q 921 - Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…], find the minimum number of conference rooms required.

Example1
Input: intervals = [(0,30),(5,10),(15,20)] ; Output: 2
Explanation:
We need two meeting rooms : room1: (0,30) and room2: (5,10),(15,20)

Example2
Input: intervals = [(2,7)] ; Output: 1
Explanation:
Only need one meeting room

Solution

Solution 1: PriorityQueue

Code:

public int minMeetingRooms(List<Interval> intervals) {

  if (intervals == null || intervals.size() == 0) return 0;

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

  PriorityQueue<Integer> pq = new PriorityQueue<>();

  pq.offer(intervals.get(0).end);

  for (int i = 1; i < intervals.size(); i++) {
    if (pq.peek() < intervals.get(i).start)
      pq.poll();
    pq.offer(intervals.get(i).end);
  }

  return pq.size();
}

Solution 2: A more concise code, using TreeMap.

Code:

public int minMeetingRooms(List<Interval> intervals) {
  Map<Integer, Integer> map = new TreeMap<>();

  for (Interval interval: intervals) {
    int start = interval.start, end = interval.end;
    map.put(start, map.getOrDefault(start, 0) + 1);
    map.put(end, map.getOrDefault(end, 0) - 1);
  }

  int res = 0, count = 0;
  for (int time: map.keySet()) {
    count += map.get(time);
    res = Math.max(res, count);
  }

  return res;
}