Easy to understand O(n) C++ : beats 97.6 % of Solutions


  • -3
    P
    bool IntervalCompare(Interval a, Interval b)
         {
             return a.start < b.start;
         }
        class Solution {
        public:
            vector<Interval> merge(vector<Interval>& intervals) {
                vector<Interval> result;
                if(intervals.size() == 0) return result;
                sort(intervals.begin(), intervals.end(), IntervalCompare);
                result.push_back(intervals[0]);
                for(int i=1; i<intervals.size(); i++)
                {
                	if(intervals[i].start <= result.back().end)	result.back().end = max(intervals[i].end, result.back().end);
                	else result.push_back(intervals[i]);
                }
                return result;
            }
        };

  • 0
    N

    You sort the list so it is n log n


  • 6
    H

    If your solution uses sort, then you can't claim the complexity of it is in O(n)!


Log in to reply
 

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