Meeting Rooms & Meeting Rooms II

TalkingData 發布于2019-08-14 17:11 / 1733人閱讀

摘要：思路這道題就是要找區間之間是否有。而的復雜度是，所以最后總的復雜度為。思路的條件依然是不同的是這題需要求房間數。還是先，指向之前有的最小的那一個。接著的是，比小，所以又放入。。的是，比大，因此出，放入。。

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();
    }

GPU云服務器云服務器 Rooms Meeting II quartus ii

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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