# Solution For Meeting Rooms Iii

Problem statement:

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…], find the minimum number of conference rooms required.

Example:
Input: [[0, 30],[5, 10],[15, 20]] Output: 2

Solution:

The problem can be solved by arranging the meeting intervals in ascending order of their start time. We can then use a min heap to keep track of the end times of the meetings that are currently happening. For each new meeting interval, we can compare its start time with the end time of the earliest (smallest) end time meeting in the min heap. If the start time of the new meeting is greater than the end time of the earliest meeting, we can replace the earliest meeting with the new meeting, as the earlier meeting has already ended. If the start time of the new meeting is less than or equal to the end time of the earliest meeting, then we need to allocate another room for the new meeting.

The number of meeting rooms required will be the size of the min heap at the end of all the iterations.

Here is the detailed step-by-step solution:

1. Sort the meeting intervals in ascending order of their start times.

2. Create a min heap to keep track of the end times of the meetings that are currently happening. Add the end time of the first meeting to the min heap.

3. Iterate through the remaining meeting intervals. For each meeting interval, compare its start time with the end time of the earliest (smallest) end time meeting in the min heap.

4. If the start time of the new meeting is greater than the end time of the earliest meeting, we can replace the earliest meeting with the new meeting, as the earlier meeting has already ended. Update the end time of the earliest meeting in the min heap to be the end time of the new meeting.

5. If the start time of the new meeting is less than or equal to the end time of the earliest meeting, then we need to allocate another room for the new meeting. Add the end time of the new meeting to the min heap.

6. The number of meeting rooms required will be the size of the min heap at the end of all the iterations.

Here is the Python code implementation:

import heapq

class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:

``````    # Sort the meeting intervals in ascending order of their start times
intervals.sort(key = lambda x: x[0])

# Create a min heap to keep track of the end times of the meetings that are currently happening
min_heap = []

# Add the end time of the first meeting to the min heap
heapq.heappush(min_heap, intervals[0][1])

# Iterate through the remaining meeting intervals
for i in range(1, len(intervals)):

# Compare the start time of the new meeting with the end time of the earliest meeting in the min heap
if intervals[i][0] >= min_heap[0]:

# Replace the earliest meeting with the new meeting, as the earlier meeting has already ended
heapq.heappop(min_heap)

# Add the end time of the new meeting to the min heap
heapq.heappush(min_heap, intervals[i][1])

# The number of meeting rooms required will be the size of the min heap at the end of all the iterations
return len(min_heap)
``````

Time Complexity:
The time complexity of this solution is O(nlogn), where n is the number of meeting intervals. The sorting takes O(nlogn) time and the min heap operations take O(nlogn) time.

Space Complexity:
The space complexity is O(n), as we need to store the meeting intervals in a list and the min heap can have at most n elements.

## Step by Step Implementation For Meeting Rooms Iii

```/**
* Definition for an interval.
* public class Interval {
*     int start;
*     int end;
*     Interval() { start = 0; end = 0; }
*     Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public int minMeetingRooms(Interval[] intervals) {
// check for the base case
if (intervals == null || intervals.length == 0)
return 0;

// sort the intervals by start time
Arrays.sort(intervals, new Comparator() {
public int compare(Interval i1, Interval i2) {
return i1.start - i2.start;
}
});

// create a min heap
PriorityQueue pq = new PriorityQueue(intervals.length, new Comparator() {
public int compare(Interval i1, Interval i2) {
return i1.end - i2.end;
}
});

// add the first interval to the queue
pq.offer(intervals[0]);

// start from the second interval and process all intervals
for (int i = 1; i < intervals.length; i++) {
// get interval from pq
Interval interval = pq.poll();

// if this interval doesn't overlap with the previous interval, then remove the previous interval from the queue
if (intervals[i].start >= interval.end) {
interval.end = intervals[i].end;
}
// otherwise, there is overlap, so we need to add a new room for the current meeting
else {
pq.offer(intervals[i]);
}

// don't forget to put the interval back
pq.offer(interval);
}

// the size of the pq tells us the minimum number of rooms needed to accommodate all the meetings
return pq.size();
}
}```
```Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

# Python Solution

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
def minMeetingRooms(self, intervals):
"""
:type intervals: List[Interval]
:rtype: int
"""

# Sort the intervals by start time
intervals.sort(key=lambda x: x.start)

# Initialize a min-heap
heap = []
# Add the first interval to the heap
heapq.heappush(heap, intervals[0].end)

# Start from the second interval and merge all intervals that can
# be merged into one.
for i in range(1, len(intervals)):
# If the start time of the current interval is greater than the
# end time of the earliest ending interval we've seen so far,
# then they can't be merged, so we need a new room.
# Otherwise, we can merge the current interval with the interval
# at the top of the heap.
if intervals[i].start >= heap[0]:
# Update the end time of the earliest ending interval we've
# seen so far
heapq[0] = intervals[i].end
else:
# Add the current interval to the heap
heapq.heappush(heap, intervals[i].end)

# The size of the heap gives us the minimum number of rooms required
return len(heap)```
```/**
* @param {number[][]} intervals
* @return {number}
*/

// sort the intervals by start time
intervals.sort((a, b) => a[0] - b[0]);

// initialize a min heap to store the end time of each interval
let heap = new Heap((a, b) => b[1] - a[1]);

// initialize a counter for the number of rooms needed
let rooms = 0;

// iterate through the intervals
for (let interval of intervals) {
// if the heap is empty, we need a new room for this interval
if (heap.isEmpty()) {
heap.push(interval);
rooms++;
// if the start time of this interval is greater than the end time of
// the interval at the top of the heap, we can reuse the room
} else if (interval[0] >= heap.peek()[1]) {
heap.pop();
heap.push(interval);
// otherwise, we need a new room
} else {
heap.push(interval);
rooms++;
}
}

// return the number of rooms needed
return rooms;```
```/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
int minMeetingRooms(vector& intervals) {
int n = intervals.size();
if (n == 0) return 0;
sort(intervals.begin(), intervals.end(), [](Interval a, Interval b) {
return a.start < b.start;
});
int count = 1;
int end = intervals[0].end;
for (int i = 1; i < n; i++) {
if (intervals[i].start < end) {
count++;
} else {
end = intervals[i].end;
}
}
return count;
}
};```
```/**
* Definition for an interval.
* public class Interval {
*     public int start;
*     public int end;
*     public Interval() { start = 0; end = 0; }
*     public Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public int MinMeetingRooms(Interval[] intervals) {
// sort the intervals by start time
Array.Sort(intervals, (a, b) => a.start.CompareTo(b.start));

// use a min heap to track the minimum end time of merged intervals
var heap = new MinHeap();

// add the first interval to the heap

for (int i = 1; i < intervals.Length; i++) {
// get the interval with the earliest end time
var interval = heap.GetMin();

if (intervals[i].start >= interval) {
// if the current interval starts after the end of the previous one,
// we can reuse the same room
heap.ReplaceMin(intervals[i].end);
} else {
// otherwise, this interval starts before the end of the previous one,
// so we need a new room
}
}

// the size of the heap is the number of rooms we need
return heap.Size();
}

private class MinHeap {
private List _heap;

public MinHeap() {
_heap = new List();
}

HeapifyUp(_heap.Count - 1);
}

public int GetMin() {
if (_heap.Count == 0) {
throw new Exception("Heap is empty");
}

return _heap[0];
}

public void ReplaceMin(int val) {
if (_heap.Count == 0) {
throw new Exception("Heap is empty");
}

_heap[0] = val;
HeapifyDown(0);
}

public int Size() {
return _heap.Count;
}

private void HeapifyUp(int index) {
while (index > 0) {
int parent = (index - 1) / 2;

if (_heap[parent] <= _heap[index]) {
break;
}

Swap(parent, index);
index = parent;
}
}

private void HeapifyDown(int index) {
while (true) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int smallest = index;

if (left < _heap.Count && _heap[left] < _heap[smallest]) {
smallest = left;
}

if (right < _heap.Count && _heap[right] < _heap[smallest]) {
smallest = right;
}

if (smallest == index) {
break;
}

Swap(smallest, index);
index = smallest;
}
}

private void Swap(int i, int j) {
var temp = _heap[i];
_heap[i] = _heap[j];
_heap[j] = temp;
}
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]