[LeetCode]Meeting Rooms II

题目链接

首先我们定义一个interval集合的深度d为，当我们用一根竖直的线L从左向右扫的时候，与L相交的intervals的数量的最大值。那么对于这道题，所要用的room的数量n，不可能小于d，因为总有某一时刻有d个meeting同时进行。n也不可能大于d，因为任何一个时刻不可能有大于d个会议同时进行。所以interval集合的深度d，就是这道题的答案，我们也将这道题，转化为求集合深度d的题目。
如何求深度d呢？我们将集合按starting time sort，从左到右遍历，并且把每一个经过的interval的end time放入优先队列，当我们访问某个interval i的时候，将优先队列里比i.start小或等的time pop出，因为这些interval已经不和当前interval相交了，记录此时的深度di，取这些值的最大值就是d。时间复杂度O(nlogn)，代码如下：


领完一种方法就是存event，event分两种，开始和结束。从左向右扫，根据event来更新当前深度即可。时间复杂度O(n * log n)，代码如下：