Meeting Room II(Medium)

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. 题解：

两种做法。都需要先根据start排序原数组。然后要么用最小堆，要么对每一个start，遍历end，比较end是否小于等于start。

public int minMeetingRooms(Interval[] intervals) {
        Arrays.sort(intervals, new IntervalComparator());
        PriorityQueue<Integer> minHeap = new PriorityQueue();
        int rooms = 0;

        for(int i = 0; i < intervals.length; i++) {
            if(minHeap.size() == 0) {
                minHeap.add(intervals[i].end);
                rooms++;
                continue;
            }

            if(minHeap.peek() <= intervals[i].start) {
                minHeap.poll();
            } else {
                rooms++;
            }

            minHeap.add(intervals[i].end);
        }
        return rooms;
    }

    class IntervalComparator implements Comparator<Interval> {
        public int compare(Interval a, Interval b) {
            return a.start - b.start;
        }
    }

    static class Interval {
        int start;
        int end;

        Interval() { start = 0; end = 0; }
        Interval(int s, int e) { start = s; end = e; }
    }



    public static void main(String args[]) throws Exception {
        Test instance = new Test();

        Interval[] nums = {new Interval(0,30),new Interval(5,10),new Interval(15,20)};

        System.out.println(instance.minMeetingRooms(nums));
    }