Fast C++ code with explanations


  • 0
    A
        int minMeetingRooms(vector<Interval>& intervals) {
            // Step 0 -- Special case.
            if(intervals.empty())
                return 0;
            
            // Step 1 -- Sort the input vector.
            sort(intervals.begin(),intervals.end(),compare);
            int bound = intervals[0].end + 1; // All meeting end times are upper-bounded by this variable.
            
            // Step 2 -- Create a vector of length n, storing the earliest meeting starting time in every room.
            int n = intervals.size();
            vector<int> est(n,bound);
                
            // Step 3 -- Starting with the first meeting in the sorted input, for every meeting, insert it 
            //           to the smallest-indexed room such that there is no conflict, or into a new room.
            int index;
            for(Interval m:intervals){
                index = 0;
                while(index<n){
                    if(m.end>est[index])
                        index++;
                    else{
                        est[index] = m.start;
                        index = n;
                    }
                }// end -- while 
                
            }// end -- for 
            
            // Step 4 -- Count how many rooms are in use.
            int count = 0;
            for(int t:est){
                if(t<bound)
                    count++;
            }// end -- for 
            
            return count;
        }
        
        static bool compare(Interval& a, Interval& b){
            return a.end >= b.end; // a goes first if true.
        }// end -- compare
        // This function is static because it does NOT access member variables.
    

Log in to reply
 

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