My 16ms C++ solution


  • 0
    P

    I first wrote my own sort function to sort the intervals but it turned out to be really slow. I have commented out my sorting function based solution in the solution below. If anyone can suggest me any way to improve it, please feel free to comment.

    My final solution here also has a section commented out . If I use that part instead, the run time increases from 16 to 20 ms and I am not sure why. If you have an answer, please let me know in the comment section. I would be truly grateful.

     class Solution {
    public:
        vector<Interval> merge(vector<Interval>& intervals) 
        {
            vector<Interval> result;
            int size = intervals.size();
            if (size < 2) return intervals;
            sort(intervals.begin(), intervals.end(), [](Interval a, Interval b) {return (a.start < b.start);});
    
            for(int i =1; i<size; i++)
            {
                if ( intervals[i-1].end >= intervals[i].start) 
                {
                    intervals[i].start = intervals[i-1].start;
                    intervals[i].end = max(intervals[i].end, intervals[i-1].end);
                }
                else 
                    result.push_back(intervals[i-1]);
            }
            result.push_back(intervals[size-1]);
    
            /*
            result.push_back(intervals[0]);
            for (int i = 1; i < size; i++) 
            {
                if (result.back().end < intervals[i].start) result.push_back(intervals[i]);
                else
                    result.back().end = max(result.back().end, intervals[i].end);
            }
             */
            return result;
        }
     };
     
    /*    My 96ms solution
    class Solution {
    public:
        vector<Interval> merge(vector<Interval>& intervals) 
        {
            vector<Interval> result, temp;
            int size = intervals.size();
            if (size < 2) return intervals;
            temp =  merge_sort(intervals);
            for(int i =1; i<size; i++)
            {
                if ( temp[i-1].end >= temp[i].start) 
                {
                    temp[i].start = temp[i-1].start;
                    temp[i].end = max(temp[i].end, temp[i-1].end);
                }
                else 
                    result.push_back(temp[i-1]);
            }
            result.push_back(temp[size-1]);
            return result;
        }
        
        vector<Interval> merge_sort(vector<Interval> intervals)
        {   
            int n = intervals.size();
            if (n == 1)
            {
                return intervals;
            }
            int mid = n/2;
            vector<Interval> left, right;
            for(int i = 0 ; i < mid; i++)
            {
                left.push_back(intervals[i]);
            }
            for(int i = mid ; i < n; i++)
            {
                right.push_back(intervals[i]);
            }
            
            left = merge_sort(left);
            right = merge_sort(right);
            return merger(left , right);
        
        }
        vector<Interval> merger(vector<Interval> l, vector<Interval> r)
        {   vector<Interval> res;
            int i = 0, j = 0;
            while(i < int(l.size()) && j < int(r.size()) )
            {   
                (l[i].start < r[j].start ) ? res.push_back(l[i++]) : res.push_back(r[j++]) ;
            }
            while (i < int(l.size())) res.push_back(l[i++]);
            while (j < int(r.size())) res.push_back(r[j++]);
            return res;
        }
    };
    */
    
    

Log in to reply
 

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