C++ solution using sweep line (set).


  • 0
    G
    /**
     * 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<Interval>& intervals) {
            
            struct Event{
                bool isStart;
                int coord;
                Interval *i;
                
                Event(bool b, int c,Interval * intr):
                    isStart(b),coord(c),i(intr){}
            };
            
            auto comp = [](const Event &e1, const Event &e2)->bool{
                if(e1.coord < e2.coord){
                    return true;
                }
                
                if(e1.coord == e2.coord){
                   if(e1.isStart == true && e2.isStart == true){
                       if(e1.i->end == e2.i->end){
                           return e1.i < e2.i;
                       }
                       
                       return e1.i->end < e2.i->end;
                   }
                    
                   return e1.isStart == false;
                }
                
                return false;
            };
            
            set<Event,decltype(comp)> allEvents(comp);
            
            for(auto &I : intervals){
                Event e1(true,I.start,&I), e2(false, I.end,&I);
                allEvents.insert(e1);
                allEvents.insert(e2);
            }
            
            int maxCount = 0;
            int currCount = 0;
            
            for(auto &s : allEvents){
                if(s.isStart){
                    currCount++;
                    maxCount = max(maxCount,currCount);
                }
                else{
                    currCount--;
                }
            }
            return maxCount;
        }
    };
    

Log in to reply
 

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