[LeetCode] 253. Meeting Rooms II

mengera88 发布于2019-08-19 11:14 / 1445人阅读

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短信平台

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

转载请注明本文地址：https://www.ucloud.cn/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

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

摘要：广度优先搜索复杂度时间空间思路实际上就是找每个房间到最近的门的距离，我们从每个门开始，广度优先搜索并记录层数就行了。这题要注意剪枝，如果下一步是门或者下一步是墙或者下一步已经访问过了，就不要加入队列中。 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