C++ Solution O(nlgn)


  • -1
    A
    class Solution {
        static bool sortfn(const Interval &a, const Interval &b) {
            return a.start <= b.start;
        }
        struct cmpObject {
            bool operator()(const Interval &a, const Interval &b) const {
                return a.start <= b.start;
            }
        };
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            sort(intervals.begin(), intervals.end(), Solution::sortfn);
            priority_queue<Interval, vector<Interval>, cmpObject> pq;
            for (auto &intvl : intervals ) {
                if (pq.empty()) { pq.push(intvl); continue; }
                
                auto top = pq.top();
                
                // case 1 - non overlapping
                if (intvl.start > top.end) { 
                    pq.push(intvl); 
                    continue; 
                }
                
                // case 2 beg2 <= end1 and end2 > end
                // merge and make a new intvl
                // pop the top and push the new intvl
                if (intvl.start <= top.end && intvl.end > top.end) {
                    Interval new_intvl(top.start, intvl.end);
                    pq.pop();
                    pq.push(new_intvl);
                    continue;
                }
                
                // case 3 new interval is completely within top interval
                // skip it
            }
            cout << pq.size() << endl;
            vector<Interval> ans;
            while(!pq.empty()) {
                auto top = pq.top();
                ans.push_back(top);
                pq.pop();
            }
            reverse(ans.begin(), ans.end());
            cout << ans.size() << endl;
            return ans;
        }
    };

Log in to reply
 

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