跳至主要內容

 

labuladong约 927 字大约 3 分钟扫描线数组排序

Info

数据结构精品课open in new window递归算法专题课open in new window 限时附赠网站会员,全新纸质书《labuladong 的算法笔记》open in new window 出版,签名版限时半价!

读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:

LeetCode力扣难度
253. Meeting Rooms IIopen in new window🔒253. 会议室 IIopen in new window🔒🟠

之前面试,被问到一道非常经典且非常实用的算法题目:会议室安排问题。

力扣上类似的问题是会员题目,你可能没办法做,但对于这种经典的算法题,掌握思路还是必要的。

先说下题目,力扣第 253 题「会议室 IIopen in new window」:

给你输入若干形如 [begin, end] 的区间,代表若干会议的开始时间和结束时间,请你计算至少需要申请多少间会议室。

函数签名如下:

// 返回需要申请的会议室数量
int minMeetingRooms(int[][] meetings);

比如给你输入 meetings = [[0,30],[5,10],[15,20]],算法应该返回 2,因为后两个会议和第一个会议时间是冲突的,至少申请两个会议室才能让所有会议顺利进行。

如果会议之间的时间有重叠,那就得额外申请会议室来开会,想求至少需要多少间会议室,就是让你计算同一时刻最多有多少会议在同时进行。

换句话说,如果把每个会议的起始时间看做一个线段区间,那么题目就是让你求最多有几个重叠区间,仅此而已。

对于这种时间安排的问题,本质上讲就是区间调度问题,十有八九得排序,然后找规律来解决。

题目延伸

我们之前写过很多区间调度相关的文章,这里就顺便帮大家梳理一下这类问题的思路:

本文剩余内容为会员内容,请先购买 网站会员 open in new window ,然后 借助 Chrome 插件解锁网页 open in new window 或者 点这里open in new window 跳转小鹅通查看。

共同维护高质量学习环境,评论礼仪见这里,违者直接拉黑不解释