9ms c++ solution based on sort and min-heap


  • 0
    Y
    int minMeetingRooms(vector<Interval>& intervals) {
            if (intervals.empty()) {
                // this case makes no sense.
                return 0;
            }
            sort(intervals.begin(), intervals.end(),
                [](const Interval& a, const Interval& b) {
                    return a.start < b.start;
                });
            
            // we should keep track of the end time to arrange meeting room;
            priority_queue<int, vector<int>, greater<int>> pq;
            pq.push(-1);
            for (int i = 0; i < intervals.size(); i++) {
                int min_end_time = pq.top();
                pq.push(intervals[i].end); // trick, trick, combine cases.
                if (intervals[i].start >= min_end_time) {
                    pq.pop();
                    continue;
                }
            }
            return pq.size();
        }
    

    In the trick line, the original code looks like

    for (int i = 0; i < intervals.size(); i++) {
        int min_end_time = pq.top();
        if (intervals[i].start >= min_end_time) {
             pq.pop();
             pq.push(intervals[i].end);
             continue;
        }
        // new meeting room since the earliest finished one is not available as well.
        pq.push(intervals[i].end);
    }
    

    We can combine the two push since if intervals[i].start >= min_end_time, we still pop out the smallest which couldn't be the one we just push in.


Log in to reply
 

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