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 协议》,转载必须注明作者和本文链接
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!