Skip to content

Latest commit

 

History

History

2406.Divide-Intervals-Into-Minimum-Number-of-Groups

2406.Divide-Intervals-Into-Minimum-Number-of-Groups

此题和253.Meeting-Rooms-II一模一样。

解法1:PQ贪心

我们将所有的会议按照开始时间排序。对于会议1而言,它占用了一个房间,那么该房间必然在某个t时刻(也就是该会议结束时间)之后才有空。然后我们查看下一个会议的开始时间,如果它在t之后,那么它就可以继续用那个房间;否则只好单开一个房间,这就意味着目前有两个房间正在被使用,我们需要了解的依然是它们各自available的时刻,那个先结束就可以更早地被重复利用。显然,我们就需要一个PQ来盛装所有正在被使用的房间,按照结束时间从早到晚排序。

所以基本的算法思想就是:对于下一个会议,查看PQ里是否有房间可以释放使用。是的话就PQ弹出该房间,并重置结束时刻再放入PQ;否则就往PQ里新增一个房间。整个过程中PQ.size()的最大值就是答案。

解法2:扫描线

利用扫描线算法可以轻松地得到最多有多少个区间同时存在。

这里需要注意的是此题允许的那个区间的左右端点是重合的。如果我们在某一个时刻累加所有的新增会议和结束会议,那么可能会得到互相抵消的结果。解决方案很巧妙,我们将所有的双闭区间处理为左闭右开的区间。对于[left,right],我们在left时刻加入会议,在right+1时刻退出会议即可。