---
# System prepended metadata

title: 0253. Meeting Rooms II
tags: [Leetcode, Priority Queue, Medium]

---

# 0253. Meeting Rooms II
###### tags: `Leetcode` `Medium` `Priority Queue`
Link: https://leetcode.com/problems/meeting-rooms-ii/
## 思路
### 思路一 $O(NlogN)$ $O(N)$
Priority Queue
用priority queue排结束的时间，每次看到新的interval，先扔掉pq里已经结束的interval，再加新的，比较pq.size()
### 思路二 $O(NlogN)$ $O(N)$
两个array分别存start的时间和end的时间，然后排序
双指针
如果下一个start的时间比end晚，指向end的指针+1，反之count+1
## Code
### 思路一
```java=
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Queue<int[]> pq = new PriorityQueue<>((a,b)->(a[1]-b[1]));
        Arrays.sort(intervals, (a,b)->(a[0]-b[0]));
        int ans = 0;
        for(int[] interval:intervals){
            while(!pq.isEmpty() && pq.peek()[1]<=interval[0]){
                pq.poll();
            }
            pq.add(interval);
            ans = Math.max(ans, pq.size());
        }
        return ans;
    }
}
```
### 思路二
```java=
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int[] start = new int[intervals.length];
        int[] end = new int[intervals.length];
        for(int i = 0;i < intervals.length;i++){
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        
        Arrays.sort(start);
        Arrays.sort(end);
        
        int room = 0;
        int endPtr = 0;
        
        for(int i = 0;i < intervals.length;i++){
            if(start[i]>=end[endPtr]){
                endPtr++;
            }
            else{
                room++;
            }
        }
        return room;
    }
}
```