专栏首页Michael阿明学习之路LeetCode 253. 会议室 II(贪心+优先队列)

LeetCode 253. 会议室 II(贪心+优先队列)

1. 题目

给定一个会议时间安排的数组,每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],…] (si < ei), 为避免会议冲突,同时要考虑充分利用会议室资源,请你计算至少需要多少间会议室,才能满足这些会议安排。

示例 1:
输入: [[0, 30],[5, 10],[15, 20]]
输出: 2

示例 2:
输入: [[7,10],[2,4]]
输出: 1

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/meeting-rooms-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

类似题目:LeetCode 252. 会议室(排序)

  • 开始时间一样,先结束的在前;开始早的在前
  • 优先队列存储会议结束的时间,堆顶是结束时间早的
  • 下一个会议开始时间早于堆顶的房间结束时间,该会议新开一个room,push进队列
  • 最后返回队列的size
class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
    	if(intervals.empty()) return 0;
    	sort(intervals.begin(), intervals.end(),[&](auto a, auto b){
    		if(a[0] == b[0])
    			return a[1] < b[1];//开始时间一样,先结束的在前
    		return a[0] < b[0];//开始早的在前
    	});
    	priority_queue<int,vector<int>,greater<int>> q;//小顶堆,存放会议室结束时间,小的在上
    	q.push(intervals[0][1]);
    	for(int i = 1; i < intervals.size(); ++i)
    	{
    		if(intervals[i][0] >= q.top())//最早结束的会议室可用,占用它
    		{
    			q.pop();
    		}
    		q.push(intervals[i][1]);
    	}
    	return q.size();
    }
};

184 ms 26.6 MB

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员面试金典 - 面试题 10.10. 数字流的秩(map/树状数组)

    假设你正在读取一串整数。每隔一段时间,你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。

    Michael阿明
  • LeetCode 第 28 场双周赛(505/2144,前23.6%)

    全国排名: 505 / 2144,23.6%;全球排名: 1944 / 8571,22.7%

    Michael阿明
  • LeetCode 223. 矩形面积

    Michael阿明
  • Codeforces Round #490 (Div. 3)

    attack
  • 洛谷P1481 魔族密码(LIS)

    attack
  • AtCoder Beginner Contest 173 A ~ F(已经补完)

    C 思路:二进制枚举 for(int i=0;i<(1<<h);i++) for(int j=0;j<(1<<w);j++) 二进制每次+1就可以暴力遍...

    用户7727433
  • Day4上午解题报告

    预计分数:50 +0+0=50 实际分数:50+0+10=60 毒瘤出题人,T3不给暴力分 (*  ̄︿ ̄)  T1 https://www.luogu.org/...

    attack
  • 【奶昔队ROUND#1】

    模拟,不过我做的时候不是模拟,是计算...(写了好久,还wa了几次),现在看了别人的代码写过一份。

    饶文津
  • 1245 最小的N个和

    1245 最小的N个和 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description ...

    attack
  • 逆元模板

    对于(a/b)%m==? 1.当m是素数的时候,根据费马小定理,直接输出b^(n-2)即可 2.否则,扩展欧几里得exgcd(b,m,x,y) 1 #incl...

    attack

扫码关注云+社区

领取腾讯云代金券