C++ O(NlogN) solution


  • 0
    H
    class Solution {
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            if(intervals.empty()) return intervals;
            auto cmp = [](Interval I1, Interval I2) {
                if(I1.start != I2.start) return I1.start < I2.start;
                else return I1.end < I2.end;
            };
            //sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){return a.start < b.start;});
            sort(intervals.begin(), intervals.end(), cmp);
            vector<Interval> ans(1, intervals[0]);
            for(int i = 1; i < intervals.size(); i ++) {
                if(intervals[i].start > ans.back().end) ans.push_back(intervals[i]);
                else ans.back().end = max(ans.back().end, intervals[i].end);
            }
            return ans;
        }
    };
    

Log in to reply
 

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