πŸ“ Problem Details

input array intervals where each interval [start,end] represents a meeting return the minimum number of conference rooms required

πŸ’­What Were My Initial Thoughts?

- we need to sort the meetings by their start time 
- need to track ongoing meetings to determine when a room becomes available
- A **min-heap (priority queue)** can be used to keep track of meeting end times:
  - If a new meeting starts after the earliest ending meeting, reuse that room.
  - Otherwise, allocate a new room.

πŸ’‘ Explanation of Solution

1. sort the intervals by start time
2. use a min heap to track end times of meetings currently occupying rooms
3. iterate through the meetings
   - if the current meeting starts **after or when** the earliest ending meeting finishes, reuse that room (pop from heap).
   - always push the current meeting's end time to the heap
4. the size of the heap at any point gives the minimum number of rooms required

βŒ› Complexity Analysis

Time Complexity: O(n log n) due to sorting and heap operations
Space Complexity: O(n) for storing elements in the heap

πŸ’» Implementation of Solution

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
 
        // Sort meetings by start time
        sort(intervals.begin(), intervals.end());
 
        // Min-heap to track end times of ongoing meetings
        priority_queue<int, vector<int>, greater<int>> minHeap;
 
        for (const auto& meeting : intervals) {
            // If the room is free (earliest meeting ended), remove it from heap
            if (!minHeap.empty() && minHeap.top() <= meeting[0]) {
                minHeap.pop();
            }
 
            // Add the current meeting's end time to the heap
            minHeap.push(meeting[1]);
        }
 
        // Heap size represents the number of rooms needed
        return minHeap.size();
    }
};