[LeetCode] 253. Meeting Rooms II

mengera88 發(fā)布于2019-08-19 11:14 / 1468人閱讀

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, 10],[15, 20]]
Output: 2
Example 2:

Input: [[7,10],[2,4]]
Output: 1

Solution Using Array

class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        //0, 100 ---- 1
        //0, 200 ---- 2
        //0, 300 ---- 3
        //150, 250 -- 3
        //160, 260 -- 4
        //210, 310 -- 4
        int n = intervals.length;
        int[] startTimes = new int[n];
        int[] endTimes = new int[n];
        for (int i = 0; i < n; i++) {
            startTimes[i] = intervals[i].start;
            endTimes[i] = intervals[i].end;
        }
        Arrays.sort(startTimes);
        Arrays.sort(endTimes);
        int count = 0;
        int i = 0, j = 0;
        while (i < n && j < n) {
            //once overlaps, room++
            if (startTimes[i] < endTimes[j]) count++;
            //not overlapping, release prev meeting room
            else j++;
            i++;
        }
        return count;
    }
}

Using Heap

class Solution {
    public int minMeetingRooms(Interval[] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> a.start-b.start);
        PriorityQueue queue = new PriorityQueue<>((a, b) -> a.end-b.end);
        /*add room for the first meeting*/
        queue.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            Interval pre = queue.poll();
            Interval cur = intervals[i];
            
            // if new meeting time overlapped, add a new room for this meeting
            if (cur.start < pre.end) queue.offer(cur);
            
            // if not overlapped, no new room for the new meeting, 
            // just update the ending time for the earliest-to-end room
            else pre.end = cur.end;
            
            // put this previous earliest-to-end room back back to heap, 
            // so that in next iteration, we get the new earliest-to-end room
            queue.offer(pre);
        }
        return queue.size();
    }
}

云服務器 GPU云服務器 Rooms Meeting 253短信接口 253短信平臺

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77272.html

[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
Meeting Rooms & Meeting Rooms II

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

TalkingData 2019-08-14 17:11 評論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
[Leetcode] Walls and Gates 墻與門

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

Edison 2019-08-14 12:48 評論0 收藏0
[Leetcode] Best Meeting Point 最佳見面點

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

王軍 2019-08-14 12:47 評論0 收藏0