C++,580ms,use stack with explanation


  • 0
    S

    use a vector to store the schedules of the rooms,
    use a stack<int> to store the schedule(we just need to focus on the end time) of one room

    class Solution {
    public:
        class compare{
            public:
            bool operator()(Interval a,Interval b){
                return a.start < b.start;
            }
        };
        int minMeetingRooms(vector<Interval>& intervals) {
            //sort the vector based on the start time;
            sort(intervals.begin(),intervals.end(),compare());
            int sz = intervals.size(),max_size=0;
            bool can_use=false;
            vector< stack<int> > vec;     //vector that store the schedule of the rooms
    
            for(int i=0;i<sz;i++){
                can_use = false;
                for(int j=0;j<vec.size();j++){
                    if(intervals[i].start>=vec[j].top()){         //if we could find an available room
                        can_use = true;
                        vec[j].push(intervals[i].end);            //push the new end time into the room schedule
                        break;
                    }
                }
                if(can_use) continue;
    
                //if we can not find an available room,push a new schedule(stack) into the vector
                stack<int> st;
                st.push(intervals[i].end);
                vec.push_back(st);
                max_size++;
            }
            return max_size;
        }
    };

Log in to reply
 

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