Implement modified quick sort and merge the end segment


  • 0
    S

    of course you can just implement an compare function and call stl sort function,
    but here, i will implement a modified version quick sort for Interval

    // a modified quick sort to sort Interval's start value
    void qSort(vector<Interval> &v, int left, int right) {
        if (left >= right) return;
        
        int low = left, high = right;
        Interval pivot = v[low];
        
        while (low < high) {
            while(low < high && v[high].start >= pivot.start)
                high--;
            if (low < high) {
                v[low].start = v[high].start;
                v[low].end = v[high].end;
                ++low;
            }
            
            while(low < high && v[low].start < pivot.start)
                low++;
            if (low < high) {
                v[high].start = v[low].start;
                v[high].end = v[low].end;
                --high;
            }
        }
        
        v[low].start = pivot.start;
        v[low].end = pivot.end;
        
        qSort(v, left, low-1);
        qSort(v, low+1, right);
    }
    
    // quick sort the inital intervals start value
    // merge the sorted end value
    vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> ans;
        int n = intervals.size();
        if (n <= 0) return ans;
        
        qSort(intervals, 0, n - 1);
        int s = 0, e = 0;
        for (int i = 0; i < n; ++i) {
            if (i == 0) {
                s = intervals[0].start;
                e = intervals[0].end;
                continue;
            }
            
            if (intervals[i].start <= e) {
                if (e < intervals[i].end)
                    e = intervals[i].end;
            }
            else {
                Interval tmp(s, e);
                ans.push_back(tmp);
                s = intervals[i].start;
                e = intervals[i].end; 
            }
        }
        
        Interval tmp(s, e);
        ans.push_back(tmp);
        return ans;
    }

  • 0
    L
    This post is deleted!

Log in to reply
 

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