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

  • 0

    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 {
    	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;
        	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
        		if(j == -1){//conflicts with all existing roomss
        	return ends.size();

Log in to reply

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