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
        heap.Add(intervals[0].end);
        
        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
                heap.Add(intervals[i].end);
            }
        }
        
        // 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();
        }
        
        public void Add(int val) {
            _heap.Add(val);
            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;
        }
    }
}