Beat 100% two different c++ solutions


  • 0
    S

    first: priority_queue and sort

    struct endcompare{
        bool operator ()(Interval& interval1, Interval& interval2){
            return interval1.end >= interval2.end;
        }
    };
    class Solution {
    private:
        static bool compare(Interval& interval1, Interval& interval2){
            if(interval1.start == interval2.start) return interval1.end <= interval2.end;
            return interval1.start <= interval2.start;
        }
    public:
        int minMeetingRooms(vector<Interval>& intervals) {
            sort(intervals.begin(),intervals.end(),compare);
            priority_queue<Interval, vector<Interval>, endcompare> pq;
            for(int i = 0; i < (int)intervals.size(); i++){
                if(!pq.empty() && intervals[i].start >= pq.top().end){
                    pq.pop();
                }
                pq.push(intervals[i]);
            }
            return pq.size();
        }
    };
    

    second: split one interval into two time node

    struct node{
        int val;
        bool start;
        node(int x, bool y):val(x), start(y){};
    };
    class Solution {
    private:
        static bool mycompare(node& n1, node& n2){
            if(n1.val == n2.val) return !n1.start;
            return n1.val < n2.val;
        }
    public:
        int minMeetingRooms(vector<Interval>& intervals) {
            vector<node> times;
            for(int i = 0; i < (int)intervals.size(); i++){
                times.push_back(node(intervals[i].start, true));
                times.push_back(node(intervals[i].end, false));
            }
            sort(times.begin(), times.end(), mycompare);
            int res = 0;
            int empty = 0;
            for(int i = 0; i < (int)times.size(); i++){
                if(times[i].start){
                    if(empty == 0){
                        res++;
                    }
                    else{
                        empty--;
                    }
                }
                else{
                    empty++;
                }
            }
            return res;
        }
    };

Log in to reply
 

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