Description

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

Given[[0, 30],[5, 10],[15, 20]],
return2.

Solution

首先对array排序，把先开始的放前面，然后用max heap，按照结束的顺序存放还没完成的会议。
注意Priority Queue初始化的时候要确定长度。

1.
/**
 * 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;
        }

        Arrays.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });

        PriorityQueue<Interval> pq= new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.end - b.end;
            }
        });

        pq.offer(intervals[0]);
        int count = 1;
        int max = 1;
        for (int i = 1; i < intervals.length; i++) {
            while (!pq.isEmpty() && pq.peek().end <= intervals[i].start) {
                pq.poll();
                count--;
            }
            pq.offer(intervals[i]);
            count++;
            max = Math.max(max, count);
        }

        return max;
    }
}

用max heap的size来记录meeting room的最大值。每次开始一个新的会议时，如果新的会议的开始时间在max heap最前面（即最早结束）的会议之后，通过把max heap最前面的会议的结束时间更新成新会议的结束时间来merge这两个会议。如果新会议在上个会议结束之前开始，意味着要增加一个meeting room，那么把新会议也放入max heap中。

2.
/**
 * 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;
        }

        Arrays.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });

        PriorityQueue<Interval> pq= new PriorityQueue<Interval>(intervals.length, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.end - b.end;
            }
        });

        pq.offer(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            // get the first meeting room that finishies earliest
            Interval interval = pq.poll();
            if (intervals[i].start >= interval.end) {
                // if current meeting starts right after, merger these two meeting rooms
                interval.end = intervals[i].end;
            } else {
                // else, add a new meeting room
                pq.offer(intervals[i]);
            }
            // put the meeting room back to heap
            pq.offer(interval);
        }

        return pq.size();
    }
}