> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/02-03-2022-253.md).

# 02/03/2022 253

Method:

First sort the 2d array by the start time. Then use Min heap to add the first element's end time. Then iterate the rest of array, compare the top value in the min heap with the new element start time. If top value <= start time of the element, then we can reuse this room.  Otherwise, we need to allocate a new room: add the new element's end time into the min heap. Noted that, if the room can be reused, we still also need to add the element's end time to the heap for the record.

Time O(nlogn)

Space O(n)

```
class Solution { public int minMeetingRooms(int[][] intervals) {

//Sort the array by the start time
Arrays.sort(intervals, (a,b) -> (a[0] - b[0]));
    
//min heap
PriorityQueue<Integer> allocator = new PriorityQueue<>();

//Add the first meeting end time;
allocator.add(intervals[0][1]);
    

for(int i = 1; i < intervals.length; i++){
    //if the top value, finish time <= the start time of the element, we can use this room
    if(allocator.peek() <= intervals[i][0]){
        allocator.poll();
    }
    //we both need to add the end time no matter the top room can be used or not.
    allocator.add(intervals[i][1]);
        
   
}
return allocator.size();
```

} }

```
public int minMeetingRooms(Interval[] intervals) {
        Map<Integer, Integer> map = new TreeMap<>();
        for (Interval itl : intervals) {
            map.put(itl.start, map.getOrDefault(itl.start, 0) + 1);
            map.put(itl.end, map.getOrDefault(itl.end, 0) - 1);
        }
        int max = 0, room = 0; 
        for (int v : map.values()) 
            max = Math.max(max, room += v); 
        
        return max; 
    }
```