Meeting Rooms Ii - Leetcode Solution

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:

1. Sort the given intervals based on their start times.
2. Create an empty priority queue that stores the end times of already scheduled meetings.
3. 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.
4. 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.

1