C++ and priority_queue


  • 0
    J

    Push meeting start and ends in priority queue,
    Pop those from the queue, ordered by time, Increment room count on every start transition, decerement on every end transition.

        int minMeetingRooms(vector<Interval>& intervals) {
            using Transition = pair<int, int>;
            auto comp = [] (const Transition& a, const Transition& b) { 
                return a.first > b.first || (a.first == b.first && a.second > b.second); 
            };
            
            priority_queue<Transition, std::vector<Transition>, decltype(comp)> q(comp);
            
            for (const auto& i : intervals) {
                q.emplace(i.start, 1);
                q.emplace(i.end, -1);
            }
            
            int maxRooms = 0;
            int cnt = 0;
            while (!q.empty()) {
                cnt += q.top().second;
                maxRooms = max(maxRooms, cnt);
                q.pop();
            }
            
            return maxRooms;
        }
    

Log in to reply
 

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