Why sort first and then merge? You can do merge when sorting


  • 0
    L

    I solved the problem using a variation of top-down merge sort, you can do bottom up if you don't like recursion. The basic idea is to do merge while sorting, and therefore you can get O(nlogn) complexity. Here is the code:

    class Solution {
    public:
        vector<Interval> merge(vector<Interval> &intervals) {
            return merge(intervals,0,intervals.size()-1);
        }
    private:
        vector<Interval> merge(vector<Interval> &intervals, int p, int q) {
            if (p >q) return {};
            if (p == q) return {intervals[p]};
            int mid = (p+q)/2;
            
            vector<Interval> leftPart = merge(intervals,p,mid);
            vector<Interval> rightPart = merge(intervals,mid+1,q);
            
            vector<Interval> combine = {};
            int i = 0,j = 0;
            while (i < leftPart.size() && j < rightPart.size()) {
                if (leftPart[i].end < rightPart[j].start)
                    insertBack(combine,leftPart[i++]);
                else if (leftPart[i].start > rightPart[j].end)
                    insertBack(combine,rightPart[j++]);
                else {
                    int newStart = (leftPart[i].start < rightPart[j].start?leftPart[i].start:rightPart[j].start);
                    int newEnd = leftPart[i].end > rightPart[j].end?leftPart[i].end:rightPart[j].end;
                    
                    Interval newInt(newStart,newEnd);
                    insertBack(combine,newInt);
                    i++;
                    j++;
                }
            }
            
            while (i < leftPart.size())
                insertBack(combine,leftPart[i++]);
            while (j < rightPart.size())
                insertBack(combine,rightPart[j++]);
            
            return combine;
        }
        void insertBack(vector<Interval> &intervals,Interval a) {
            if (intervals.empty())
                intervals.push_back(a);
            else {
                Interval last = intervals.back();
                if (last.end < a.start)
                    intervals.push_back(a);
                else if (last.end < a.end) {
                    intervals.pop_back();
                    intervals.push_back(Interval(last.start,a.end));
                }
                else {
                    //last.end >= a.end, do nothing
                }
            }
            
        }
    
    };

  • 2
    J

    Well, the code is messy and I bet you won't look at it again. Sorting and looping do not hurt much.


Log in to reply
 

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