Self-defined compare of the struct & one loop


  • 1
    /**
     * Definition for an interval.
     * struct Interval {
     *     int start;
     *     int end;
     *     Interval() : start(0), end(0) {}
     *     Interval(int s, int e) : start(s), end(e) {}
     * };
     */
     
    bool compare(Interval& a, Interval& b){
        return a.start==b.start ? a.end<b.end : a.start<b.start;
    }
    class Solution {
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            int n=intervals.size();
            vector<Interval> result;
            if(n==0)  return  result;
            sort(intervals.begin(), intervals.end(), compare);
            for(int i=0; i<n; i++){
                int index=result.size();
                if(index>0 && result[index-1].end >= intervals[i].start){
                    result[index-1].end=max(result[index-1].end, intervals[i].end);
                }
                else{
                    result.push_back(intervals[i]);
                }
            }
            return result;
        }
    };

  • 0
    2

    Really concise implementation , here is the AC implementation ...

    bool compare(Interval& a, Interval& b) {
    return a.start == b.start ? a.end < b.end : a. start < b.start;
    }

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

Log in to reply
 

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