My easy C++ solution


  • 11
    Z
    static bool comp(const Interval& a, const Interval& b){
        return a.start < b.start;
    }
    vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> result;
        if(intervals.empty()){
            return result;
        }
        sort(intervals.begin(), intervals.end(), comp);
        result.push_back(intervals[0]);
        for(int i = 1; i < intervals.size(); i++){
            if(intervals[i].start <= result.back().end){
                Interval temp(result.back().start, max(result.back().end, intervals[i].end));
                result.pop_back();
                result.push_back(temp);
            }
            else{
                result.push_back(intervals[i]);
            }
        }
        return result;
    }

  • 1
    X

    result.pop_back(); result.push_back(temp);

    you don't need these two lines;

    result.back(0.end = max(result.back().end, intervals[i].end);


  • 0
    N

    What a concise solution


  • 0
    H

    I use this comp function and get a runtime error for a long test dataset.....

    static bool comp (const Interval& l, const Interval& r) {

    if (l.start < r.start) {

    return true;

    }

    else if (l.start == r.start) {

    return l.end <= r.end;

    }

    else return false;

    }


  • 0
    L

    Can somebody please tell me why my solution is showing time limited exceeded. Time complexity if O(nlogn) here of sorting the intervals. Intervals are merged in O(n).

    class Solution {
    public:
        static bool my_sort_func(Interval a,Interval b)
        {
            return (a.start <= b.start);
        }
        
        vector<Interval> merge(vector<Interval>& intervals) {
            
            Interval temp_interval;
            int size=intervals.size(), last_idx=0, initial_start_val=0;
            vector<Interval> result_v;
            
            sort(intervals.begin(),intervals.end(),my_sort_func);
            
            for(int i=0;i<=size-1;i++)
            {
                last_idx = intervals[i].end;
                initial_start_val = intervals[i].start;
                
                for(int j=i+1;j<=size-1;j++)
                {
                    if(last_idx >= intervals[j].start)
                    {
                        if(intervals[j].end > last_idx)
                             last_idx = intervals[j].end;
                        i++;
                    }
                    else
                        break;
                }
                
                temp_interval.start = initial_start_val;
                temp_interval.end = last_idx;
                result_v.push_back(temp_interval);
            }
            
            return result_v;
        }
    };

  • 0
    G

    Hi, my approach is quite similar to yours. I fixed bug of not claiming the operator function as a static one by comparing with yours. Could you(or anyone who knows) explain why should the operator function be static?


Log in to reply
 

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