# Implement modified quick sort and merge the end segment

• 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;
}``````

• This post is deleted!

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