## Approach 1: Heap

• Time:O(n\log n)
• Space:O(n)

## C++

``````class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
// store end times of each room
priority_queue<int, vector<int>, greater<>> minHeap;

sort(begin(intervals), end(intervals));

for (const auto& interval : intervals) {
if (!minHeap.empty() && interval[0] >= minHeap.top())
minHeap.pop();  // no overlap, we can reuse the same room
minHeap.push(interval[1]);
}

return minHeap.size();
}
};
``````

## JAVA

``````class Solution {
public int minMeetingRooms(int[][] intervals) {
// store end times of each room
Queue<Integer> minHeap = new PriorityQueue<>((a, b) -> a - b);

Arrays.sort(intervals, (a, b) -> (a[0] - b[0]));

for (int[] interval : intervals) {
if (!minHeap.isEmpty() && interval[0] >= minHeap.peek())
minHeap.poll(); // no overlap, we can reuse the same room
minHeap.offer(interval[1]);
}

return minHeap.size();
}
}
``````

## Python

``````class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
minHeap = []  # store end times of each room

for start, end in sorted(intervals):
if minHeap and start >= minHeap[0]:
heapq.heappop(minHeap)
heapq.heappush(minHeap, end)

return len(minHeap)
``````

## Approach 2: Sort

• Time:O(n\log n)
• Space:O(n)

## C++

``````class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
const int n = intervals.size();
int ans = 0;
vector<int> starts;
vector<int> ends;

for (const auto& interval : intervals) {
starts.push_back(interval[0]);
ends.push_back(interval[1]);
}

sort(begin(starts), end(starts));
sort(begin(ends), end(ends));

for (int i = 0, j = 0; i < n; ++i)
if (starts[i] < ends[j])
++ans;
else
++j;

return ans;
}
};
``````

## JAVA

``````class Solution {
public int minMeetingRooms(int[][] intervals) {
final int n = intervals.length;
int ans = 0;
int[] starts = new int[n];
int[] ends = new int[n];

for (int i = 0; i < n; ++i) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}

Arrays.sort(starts);
Arrays.sort(ends);

// j points to ends
for (int i = 0, j = 0; i < n; ++i)
if (starts[i] < ends[j])
++ans;
else
++j;

return ans;
}
}
``````

## Python

``````class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
n = len(intervals)
ans = 0
starts = []
ends = []

for start, end in intervals:
starts.append(start)
ends.append(end)

starts.sort()
ends.sort()

j = 0
for i in range(n):
if starts[i] < ends[j]:
ans += 1
else:
j += 1

return ans
``````