Meeting Rooms & Meeting Rooms II

TalkingData 发布于2019-08-14 17:11 / 1692人阅读

摘要：思路这道题就是要找区间之间是否有。而的复杂度是，所以最后总的复杂度为。思路的条件依然是不同的是这题需要求房间数。还是先，指向之前有的最小的那一个。接着的是，比小，所以又放入。。的是，比大，因此出，放入。。

Meeting Rooms

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

思路
这道题就是要找区间之间是否有overlap。对一个区间来说被别的区间overlap有三种情况：

完全覆盖：比如[5, 6]和[3, 7]，区间[5, 6]完全被[3, 7]覆盖

前一部分被覆盖：比如[5, 7]和[3, 6]，区间[5, 7]的前面一部分被[3, 6]覆盖

后一部分被覆盖：比如[5, 8]和[7, 9]

不管是哪种，都满足条件intervals[i].end > intervals[j].start

Sort
直接两两比较时间复杂度是O(N^2)。为了降低复杂度，可以先sort一下intervals，根据start来sort，这样j就变成i+1，比较的复杂度变成O(N)。而sort的复杂度是O(NlogN)，所以最后总的复杂度为O(NlogN)。java8里面sort可以用lambada表达式写。

    public boolean canAttendMeetings(Interval[] intervals) {
        // base case
        if(intervals == null || intervals.length == 0) return true;
        
        // sort
        Arrays.sort(intervals, (a, b) -> a.start == b.start ? a.end - b.end : a.start - b.start);
        
        for(int i = 0; i < intervals.length - 1; i++) {
            if(intervals[i].end > intervals[i+1].start) return false;
        }
        return true;
    }

Meeting Rooms II

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.

思路
overlap的条件依然是：intervals[i].end > intervals[j].start
不同的是这题需要求房间数。还是先sort，i指向之前有overlap的最小end的那一个。

复杂度
Time Complexity: O(NlogN)，Space: O(N)。

heap
因为要知道之前有overlap的最小的end，所以可以用一个min heap。每次检查新的start是否比heap的top元素小，是的话就把保存原来的end，同时放进新的end；否则就放新的end同时poll出原来的，因为没有overlap且新的end较大。最后heap的大小就是需要的房间数。比如：
[1, 5], [2, 4], [3, 6], [5, 7]

heap: [5]。[2, 4]的start是2，比5小，所以放入4。

heap: [4, 5]。接着[3 ,6]的start是3，比4小，所以又放入6。

heap: [4, 5, 6]。[5, 7]的start是5，比4大，因此poll出4，放入7。

heap: [5, 6, 7]。最后heap的size为3。

4被pop出来是因为[2, 4]和[5, 7]公用一个房间，只要放7进去就可以了。

    public int minMeetingRooms(Interval[] intervals) {
        // base case
        if(intervals == null || intervals.length == 0) return 0;
        // sort
        Arrays.sort(intervals, (a, b) -> a.start == b.start ? a.end - b.end : a.start - b.start);
        // min heap to store the end
        PriorityQueue minHeap = new PriorityQueue<>();
        minHeap.offer(intervals[0].end);
        for(int i = 1; i < intervals.length; i++) {
            // no overlap
            if(minHeap.peek() <= intervals[i].start) minHeap.poll();
            minHeap.offer(intervals[i].end);
        }
        
        return minHeap.size();
    }

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66479.html

[LeetCode] 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. Example 1: Input: [[0, 30],[5,...

mengera88 2019-08-19 11:14 评论0 收藏0
[Leetcode] Meeting Rooms 会议室

摘要：排序法复杂度时间空间思路这题和很像，我们按开始时间把这些都给排序后，就挨个检查是否有冲突就行了。有冲突的定义是开始时间小于之前最晚的结束时间。这里之前最晚的结束时间不一定是上一个的结束时间，所以我们更新的时候要取最大值。 Meeting Rooms Given an array of meeting time intervals consisting of start and end...

jubincn 2019-08-14 12:47 评论0 收藏0
[LintCode/LeetCode] Meeting Rooms

Problem Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings. Example Given intervals = [[0,30],[...

Noodles 2019-08-16 12:34 评论0 收藏0
泛化&amp;泛化数据集&amp;实验

摘要：泛化泛化数据集实验泛化过拟合的风险泛化泛化能力是指机器学习算法对新鲜样本的适应能力。机器学习的基本冲突是适当拟合我们的数据，但也要尽可能简单地拟合数据。使用测试集再次检查该模型。特征通常在正常范围内，其中第百分位数的值约为。泛化&泛化数据集&实验泛化 (Generalization)：过拟合的风险泛化:泛化能力（generalization ability）是指机器学习算法对新...

SimpleTriangle 2019-07-31 11:06 评论0 收藏0
Walls and Gates

摘要：题目链接这道题感觉是那道的简化版，思路都是一样的。是把所有的点都先放到里面，然后一起遍历。这种写法的好处是保证了每个点都只被放进一次，不会重复遍历。保证了时间复杂是。可以不写成层次遍历的形式，直接，的程序 Walls and Gates 题目链接：https://leetcode.com/problems... 这道题感觉是那道Shortest Distance from All Bu...

CKJOKER 2019-08-14 17:18 评论0 收藏0