15ms C++ using map (97%)


  • 0
    M
    vector<Interval> merge(vector<Interval>& intervals) {
            vector<Interval> res;
            map<int, int> m;
            for(Interval i : intervals){
                m[i.start]++;  //start point increase the counter
                m[i.end]--;     //end point decrease the counter
            }
    
            //sum up the nums by iterating all the time stamps, when the sum equals 0 means current time is the end of current interval
            int sum = 0;
            for(auto p : m){
                if(res.empty() || res.back().end >= 0){
                    res.push_back(Interval(p.first, -1));
                }
                sum += p.second;
                if(sum == 0){
                    res.back().end = p.first;
                }
            }
            return res;
        }
    

Log in to reply
 

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