Solution For Meeting Rooms Ii
Problem statement:
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.
Example 1:
Input: [[0, 30],[5, 10],[15, 20]] Output: 2
Example 2:
Input: [[7,10],[2,4]] Output: 1
Solution:
This problem can be solved using the greedy approach and with the help of priority queue. We can first sort the given intervals based on their start times. Then, we can maintain a priority queue that stores the end times of already scheduled meetings. We will iterate through each meeting and check if any meeting in the priority queue ends before the current meeting starts. If yes, we can reuse that room for the current meeting. Otherwise, we need to allocate a new room for the current meeting.
Algorithm:
- Sort the given intervals based on their start times.
- Create an empty priority queue that stores the end times of already scheduled meetings.
- Iterate through each interval in the sorted intervals:
a. If the priority queue is empty or the earliest end time in the priority queue is greater than the start time of the current interval, allocate a new room for the current interval.
b. Otherwise, pop the earliest end time from the priority queue and push the end time of the current interval into the priority queue. - The size of the priority queue at any point of time represents the number of rooms needed.
Code:
The code in Python for this problem is as follows:
“`
from queue import PriorityQueue
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: x[0])
pq = PriorityQueue()
for interval in intervals:
if pq.empty() or pq.queue[0] > interval[0]:
pq.put(interval[1])
else:
pq.get()
pq.put(interval[1])
return pq.qsize()
“`
Time complexity:
The time complexity of this solution is O(nlogn), where n is the total number of intervals. The sorting operation takes O(nlogn) time and the priority queue operations take O(logn) time for each interval.
Step by Step Implementation For Meeting Rooms Ii
/**
* 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; }
* }
*/
class Solution {
public int minMeetingRooms(Interval[] intervals) {
// check for the base case
if (intervals.length == 0) {
return 0;
}
// sort the intervals by start time
Arrays.sort(intervals, new Comparator() {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
});
// create a min heap
PriorityQueue heap = new PriorityQueue(intervals.length, new Comparator() {
public int compare(Interval a, Interval b) {
return a.end - b.end;
}
});
// add the first interval to the heap
heap.offer(intervals[0]);
// start from the next interval and merge if necessary
for (int i = 1; i < intervals.length; i++) {
// get interval from heap
Interval interval = heap.poll();
// if the current interval starts after the end of the previous one,
// then they can share the same room
if (intervals[i].start >= interval.end) {
interval.end = intervals[i].end;
} else {
// otherwise, a new room is needed
heap.offer(intervals[i]);
}
// don't forget to put the interval back
heap.offer(interval);
}
// the size of the heap tells us the minimum number of rooms needed
return heap.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.
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
# Sort the given meetings by their start time.
# Initialize a new min heap and add the first meeting's ending time to the heap. We simply need to keep track of the ending times as that tells us when a meeting room will get free.
# For every meeting room check if the minimum element of the heap i.e. the room at the top of the heap is free or not.
# If the room is free, then we extract the topmost element and add it back with the ending time of the current meeting we are processing.
# If not, then we allocate a new room and add it to the heap.
# After processing all the meetings, the size of the heap tells us the number of rooms allocated. This will be the minimum number of rooms needed to accommodate all the meetings.
def minMeetingRooms(self, intervals):
if not intervals:
return 0
# Sort the meetings in increasing order of their start time.
intervals.sort(key= lambda x: x.start)
# Add the first meeting. We have to give a new room to the first meeting.
min_heap = []
heappush(min_heap, intervals[0].end)
# For all the remaining meeting rooms
for i in range(1, len(intervals)):
# If the room due to free up the earliest is free, assign that room to this meeting.
if min_heap[0] <= intervals[i].start:
heappop(min_heap)
# If a new room is to be assigned, then also we add to the heap,
# If an old room is allocated, then also we have to add to the heap with updated end time.
heappush(min_heap, intervals[i].end)
# The size of the heap tells us the minimum rooms required for all the meetings.
return len(min_heap)/**
* @param {number[][]} intervals
* @return {number}
*/
// Sort the given intervals by start time.
// Initialize a new min-heap and add the first interval to it. We don't need to extract anything from the heap yet.
// For each remaining interval:
// If the current interval starts after the top of the heap finishes, we can reuse the same room.
// Otherwise, we extract the top interval from the heap, which frees up a new room, and then add the current interval to the heap.
// After we've processed all intervals, the size of the heap tells us the minimum number of rooms we needed.
var minMeetingRooms = function(intervals) {
if (!intervals.length) return 0;
intervals.sort((a, b) => a[0] - b[0]);
let heap = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
let currentInterval = intervals[i];
let earliestEndingInterval = heap[0];
if (currentInterval[0] >= earliestEndingInterval[1]) {
heap.shift();
}
heap.push(currentInterval);
}
return heap.length;
};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.
/**
* 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, greater> pq;
pq.push(intervals[0].end);
for(int i=1;i
/**
* 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) {
if (intervals.Length == 0) {
return 0;
}
// Sort the intervals by start time
Array.Sort(intervals, (a, b) => a.start - b.start);
// Use a min heap to track the minimum end time of merged intervals
var heap = new SortedList();
// Start with the first meeting, put it to a meeting room
heap.Add(intervals[0].end, 1);
for (int i = 1; i < intervals.Length; i++) {
// Get the meeting room that finishes earliest
var interval = intervals[i];
var earliest = heap.Keys[0];
if (interval.start >= earliest) {
// This meeting starts right after another meeting ends,
// merge those two meetings into one
var count = heap[earliest];
heap.Remove(earliest);
heap.Add(interval.end, count);
}
else {
// This meeting starts before another meeting ends,
// allocate a new meeting room
heap.Add(interval.end, 1);
}
}
// The size of the heap tells us the minimum number of meeting rooms we need
return heap.Values.Sum();
}
} 