Concise C++ Solution with min_heap, sort, greedy


  • 15
    I
    // greedy : always change the smallest end time;
    // heap : min_heap
    // sort : sort the intervals by start time O(nlogn)
    int minMeetingRooms(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), [](Interval &i, Interval &j){return i.start < j.start;});
        priority_queue<int, vector<int>, greater<int>> min_heap;
        for(auto interval : intervals){
            if(!min_heap.empty() && min_heap.top() <= interval.start) min_heap.pop();
            min_heap.push(interval.end);
        }
        return min_heap.size();
    }

  • 0
    M
    This post is deleted!

  • 0
    C

    the best solution i've ever seen. thank you!


  • 0

    The best and concise C++ solution I have seen so far!


Log in to reply
 

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