253. Meeting Rooms II

解法一：数组排序

思路

将回忆间隔分为开始和结束两个数组，按照从小到大顺序排序。要寻找一个会议开始时间是否和其他会议的最早结束时间冲突。
那么，如果一个会议的开始时间在最早结束时间前开始，就需要一个房间，反之可以在其后面进行会议。如果一个会议开始时间大于最早结束时间，不需要额外房间，但最早的结束时间需要向后移动一个位置。
举例：如 start = [1,3,5,15,35]; end = [9, 11, 26, 30, 33] 那么1,3,5都在最早结束时间9的前面，所以都需要额外房间。此时房间数为3。15在9后面，所以不用额外安排时间，而最早结束时间变为11。35在11后面，所以也不用额外安排房间。所以总的房间数为3。

代码

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        /*
        Sepearate the start and end to two arrays and sort them by ascending order
        Assign the earlist end time to be end[0];
        Initialize num of room = 0;
        for each start time
            if (start time > end time)
                earlist end time move to next end[];
            else
                num++
            end if 
        end for each
        */
        int len =  intervals.length;
        // 首先想到数组为空的情况
        if (len == 0 || intervals == null) return 0;

        int[] start = new int[len];
        int[] end = new int[len];
        for (int i = 0; i < len; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        int earlistIndex = 0;
        int num = 0;
        for (int i = 0; i < len; i++) {
            if (start[i] >= end[earlistIndex]) { // 要注意 edge case, 开始时间和结束时间相等也不用额外安排房间
                earlistIndex++;
            }
            else {
                num++;
            }
        }
        return num;
    }
}

时间复杂度：O(nlogn)，因为排序花费O(nlogn)，遍历开始时间花费O(n)。
空间复杂度: O(n), 因为使用了两个数组去储存时间。

解法二：MinHeap

思路

依然是将元素按开始时间排序，并比较之前会议的最早结束时间是否与当前会议的开始时间重合。
将数组中元素按照开始时间从大到小排序；
定义一个PriorityQueue，按照结束时间从小到大储存intervals；
从已经排序的数组中取出间隔，如果开始时间和最早结束时间重合，存入PriorityQueue中；
否则，将最早结束时间扩散至当前会议的结束时间。

代码

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int len = intervals.length;
        if (len == 0 || intervals == null) {
             return 0;
        }
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] a, int[]b) {
                return a[0] - b[0];
            }
        });

        PriorityQueue<int[]> minHeap  = new PriorityQueue<>(intervals.length, new Comparator<int[]>(){
            public int compare (int[] a, int[]b) {
                return a[1] - b[1];
            }
        });
        minHeap.offer(intervals[0]);
        // Start from the next element because the first one is already in the heap.
        for (int i = 1; i < len; i ++) {
            int[] earlistEnding = minHeap.poll();
            // No overlap, append the ending time
            if (intervals[i][0] >= earlistEnding[1]) {
                earlistEnding[1] = intervals[i][1];
            }
            // Overlap,  add a new room
            else
            {
                minHeap.offer(intervals[i]);
            }
            minHeap.offer(earlistEnding);
        }
        return minHeap.size();
    }
}

时间复杂度 O(nlogn), 空间复杂度 O(n)。

Takeaway

• 注意空数组情况和 edge cases。
• PriorityQueue 的使用：
  • 创建：PriorityQueue<Integer> p = new PriorityQueue<>(); // 默认最小值在头部
  • 使用：poll()：弹出头部的元素；offer()：添加新的元素，按照规定的排序顺序排列。
• 自定义排序顺序
  • Override (标准方法)
    • PriorityQueue<int[]> q = new PriorityQueue<>(size, new Comaprator<int[]>(){ public int new comapre(int[] a, int[] b){ return a[1] - b[1]; } });
  • lamda 表达式（简化方法）PriorityQueue<int[]> q = new PriorityQueue<>(size, (int[] a, int[] b)->(a[1] - b[1]));

本作品采用《CC 协议》，转载必须注明作者和本文链接