Simple Greedy Solution in C++


  • 0
    W

    The idea is keep track of all visited node. If a node is not visited, then keep visiting all nodes that are not overlapping with its previous node.

    class Solution {
    public:
        int minMeetingRooms(vector<Interval>& intervals) {
            if (intervals.size() == 0) return false;
            sort(intervals.begin(), intervals.end(), 
                [](const Interval &interval1, const Interval &interval2){
                    return interval1.start < interval2.start;
                });
            
            vector<bool> visited(intervals.size(), false);
            int result = 0;
            for (int i = 0; i < intervals.size(); i++){
                if (!visited[i]){
                    result++;
                    Interval prev = intervals[i];
                    for(int j = i+1; j < intervals.size(); j++){
                        if (!visited[j] && intervals[j].start >= prev.end){
                            visited[j] = true;
                            prev = intervals[j];
                        }
                    }
                }
            }
            return result;
        }
    };

Log in to reply
 

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