C++ non-greedy O(n^2) algorithm 16ms


  • 0
    Y

    I'm just curious, but the non-greedy algorithm also works. Each time we add a new room, if it conflicts with any existing room, we add a new room. If it does not conflict with some room in the vector, we use this room.

    class Solution {
    public:
    	static bool myfunction(Interval& a, Interval& b){
    		return a.start < b.start;
    	}	
        int minMeetingRooms(vector<Interval>& intervals) {
        	const int N = intervals.size();
        	if(N == 0) return 0;
            std::sort (intervals.begin(), intervals.end(), myfunction);
        	std::vector<int> ends;
    
        	ends.push_back(intervals[0].end);
        	for(int i = 1; i < N; ++i){
        		int j;
        		for(j = ends.size()-1; j >= 0; --j){
        			if(intervals[i].start >= ends[j]){ //does not conflict with some room
        				ends[j] = intervals[i].end; // use this room
        				break;
        			}
        		}
        		if(j == -1){//conflicts with all existing roomss
        			ends.push_back(intervals[i].end);
        		}
        	}
        	return ends.size();
        }
    };
    

Log in to reply
 

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