253. Meeting Rooms II

Problem:

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.

Analysis:

Approach 1: 

把start和end分别提取出来存在数组里面，然后排序。中心思想就是，如果meeting start，需要一个room。meeting end释放一个room。

按照时间顺序，s1开始，room == 1. s2开始第一个meeting没有结束，那么room++. s3开始也没有结束 room == 3. 当到s4的时候，前面有会议结束，至少会有一个room释放出来，所以不再需要新增room. s4其实是继续使用interval[0]的room.

/**
 * 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;
        int len = intervals.length;
        int[] starts = new int[len];
        int[] ends = new int[len];
        for(int i = 0; i < len; i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }

        Arrays.sort(starts);
        Arrays.sort(ends);

        int rooms = 0, endIdx = 0;
        for(int i = 0; i < len; i++) {
            if(starts[i] < ends[endIdx]) {
                rooms++;
            } else {
                endIdx++;
            }
        }
        return rooms;
    }
}

Approach 2:

我自己想出来的用skyline problem原来，无脑扫描。遇到start room++， 遇到end room--。记录下最大的room。 唯一值得注意的是当start == end 的时候，把end排在前面。

/**
 * 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;
        PriorityQueue<int[]> heap = new PriorityQueue<>(intervals.length, (a,b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int rooms = 0, res = 0;
        for (Interval i: intervals) {
            heap.offer(new int[]{i.start, 1});
            heap.offer(new int[]{i.end, -1});
        }

        while(!heap.isEmpty()) {
            res = Math.max(res, rooms += heap.poll()[1]);
        }
        return res;
    }
}