成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Meeting Rooms 會議室

jubincn / 518人閱讀

摘要：排序法復(fù)雜度時間空間思路這題和很像，我們按開始時間把這些都給排序后，就挨個檢查是否有沖突就行了。有沖突的定義是開始時間小于之前最晚的結(jié)束時間。這里之前最晚的結(jié)束時間不一定是上一個的結(jié)束時間，所以我們更新的時候要取最大值。

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.


For example, Given [[0, 30],[5, 10],[15, 20]], return false.
排序法 復(fù)雜度

時間 O(NlogN) 空間 O(1)

思路

這題和Merge Intervals很像，我們按開始時間把這些Interval都給排序后，就挨個檢查是否有沖突就行了。有沖突的定義是開始時間小于之前最晚的結(jié)束時間。這里之前最晚的結(jié)束時間不一定是上一個的結(jié)束時間，所以我們更新的時候要取最大值。

代碼 
public class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return true;
        Arrays.sort(intervals, new Comparator(){
            public int compare(Interval i1, Interval i2){
                return i1.start - i2.start;
            }
        });
        int end = intervals[0].end;
        // 檢查每一個Interval
        for(int i = 1; i < intervals.length; i++){
            // 如果Interval的開始時間小于之前最晚的結(jié)束時間，就返回假
            if(intervals[i].start < end) return false;
            end = Math.max(end, intervals[i].end);
        }
        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.


For example, Given [[0, 30],[5, 10],[15, 20]], return 2.
貪心法 復(fù)雜度

時間 O(NlogN) 空間 O(1)

思路

這題的思路和Rearrange array to certain distance很像，我們要用貪心法，即從第一個時間段開始，選擇下一個最近不沖突的時間段，再選擇下一個最近不沖突的時間段，直到?jīng)]有更多。然后如果有剩余時間段，開始為第二個房間安排，選擇最早的時間段，再選擇下一個最近不沖突的時間段，直到?jīng)]有更多，如果還有剩余時間段，則開辟第三個房間，以此類推。這里的技巧是我們不一定要遍歷這么多遍，我們實(shí)際上可以一次遍歷的時候就記錄下，比如第一個時間段我們放入房間1，然后第二個時間段，如果和房間1的結(jié)束時間不沖突，就放入房間1，否則開辟一個房間2。然后第三個時間段，如果和房間1或者房間2的結(jié)束時間不沖突，就放入房間1或者2，否則開辟一個房間3，依次類推，最后統(tǒng)計開辟了多少房間。對于每個房間，我們只要記錄其結(jié)束時間就行了，這里我們查找不沖突房間時，只要找結(jié)束時間最早的那個房間。
這里還有一個技巧，如果我們把這些房間當(dāng)作List來管理，每次查詢需要O(N)時間，如果我們用堆來管理，可以用logN時間找到時間最早結(jié)束的房間。

代碼 
public class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals, new Comparator(){
            public int compare(Interval i1, Interval i2){
                return i1.start - i2.start;
            }
        });
        // 用堆來管理房間的結(jié)束時間
        PriorityQueue endTimes = new PriorityQueue();
        endTimes.offer(intervals[0].end);
        for(int i = 1; i < intervals.length; i++){
            // 如果當(dāng)前時間段的開始時間大于最早結(jié)束的時間，則可以更新這個最早的結(jié)束時間為當(dāng)前時間段的結(jié)束時間，如果小于的話，就加入一個新的結(jié)束時間，表示新的房間
            if(intervals[i].start >= endTimes.peek()){
                endTimes.poll();
            }
            endTimes.offer(intervals[i].end);
        }
        // 有多少結(jié)束時間就有多少房間
        return endTimes.size();
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/64705.html

相關(guān)文章

  • [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 評論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 評論0 收藏0

  • Meeting Rooms & Meeting Rooms II

    摘要：思路這道題就是要找區(qū)間之間是否有。而的復(fù)雜度是，所以最后總的復(fù)雜度為。思路的條件依然是不同的是這題需要求房間數(shù)。還是先，指向之前有的最小的那一個。接著的是，比小，所以又放入。。的是，比大，因此出，放入。。 Meeting Rooms Given an array of meeting time intervals consisting of start and end times [[...

    TalkingData 評論0 收藏0

  • [Leetcode] Walls and Gates 墻與門

    摘要：廣度優(yōu)先搜索復(fù)雜度時間空間思路實(shí)際上就是找每個房間到最近的門的距離，我們從每個門開始，廣度優(yōu)先搜索并記錄層數(shù)就行了。這題要注意剪枝，如果下一步是門或者下一步是墻或者下一步已經(jīng)訪問過了，就不要加入隊列中。 Walls and Gates You are given a m x n 2D grid initialized with these three possible values....

    Edison 評論0 收藏0

  • [Leetcode] Best Meeting Point 最佳見面點(diǎn)

    摘要：為了盡量保證右邊的點(diǎn)向左走，左邊的點(diǎn)向右走，那我們就應(yīng)該去這些點(diǎn)中間的點(diǎn)作為交點(diǎn)。由于是曼哈頓距離，我們可以分開計算橫坐標(biāo)和縱坐標(biāo)，結(jié)果是一樣的。 Best Meeting Point A group of two or more people wants to meet and minimize the total travel distance. You are given a ...

    王軍 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<