Greeedy approach to Meeting Rooms II


  • 0
    H

    Problem link is here : https://leetcode.com/problems/meeting-rooms-ii/description/

    This problem can be simply solved using the greedy approach. First of all, sort all the meetings by their start timing. Now, we will pick the meeting that starts early and try to find a room for it. Rooms are nothing but a heap with their end times. The room that is freeing up early is on the top of this heap. Therefore, if top of the heap has end time that is before the start time of next meeting then pop this room out. Push the end time of new meeting back in the heap. Minimum number of rooms needed are equal to the maximum size of this heap at any time.

    #include <algorithm>
    
    #define max(a,b) (a>b?a:b)
    
    class CompareEndTimes {
    public: 
    CompareEndTimes(){}    
        bool operator()(const Interval& i1, const Interval& i2) const { return i1.start < i2.start; }
    };
    
    class LTH {
    
    public: 
        LTH(){} 
        bool operator()(const int &a, const int& b) const {return a>b;}
    };
    
    class Solution {
    
    public:
    
        int minMeetingRooms(vector<Interval>& intervals) {
            
            int minrooms = 0;
            priority_queue<int, vector<int>, LTH> rooms;
            
            std::sort(intervals.begin(), intervals.end(), CompareEndTimes());
            
            for(int i=0;i<intervals.size();i++)
            {
                if (rooms.size() != 0 && rooms.top() <= intervals[i].start) 
                    rooms.pop();
                
                rooms.push(intervals[i].end);            
                minrooms = max(minrooms, rooms.size());
            }
            
            return minrooms;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.