题目
给定一个二维数组, 数组里面包含的子数组都是一个闭区间, 合并这些区间.
Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Input: [[4,5],[1,4]]
Output: [[1,5]]
思路
先排序, 然后依次合并.
关键在于排序方法, 使用快速排序可以达到50%的速度吧, 不知道继续如何提升速度.
void quickSort(vector<vector<int>>& vec, int low, int high) {
if (low >= high) {
return;
}
int i = low;
int j = high;
vector<int> key = vec[i];
while (i<j) {
while (i<j && vec[j][0] >= key[0]) {
j--;
}
if (i == j) { // 当key是目前最小的数时，会出现i=j的情况，
break;
}
vec[i++] = vec[j]; // i++ 会减少一次m[i]和key的比较
while (i < j && vec[i][0] <= key[0]) {
i++;
}
if (i == j) { // 当key是目前最大的数时(m[j]的前面)，会出现i=j的情况
break;
}
vec[j--] = vec[i]; //j-- 会减少一次m[j]和key的比较
}
vec[i] = key;
quickSort(vec, low, i-1);
quickSort(vec, i+1, high);
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.size() <= 1) {
return intervals;
}
quickSort(intervals, 0, intervals.size() - 1);
vector<vector<int>> result;
map<vector<int>, int> map;
vector<int> tmp = intervals[0];
for (int i = 1;i < intervals.size();i++) {
vector<int> next = intervals[i];
if (tmp[0] <= next[0] && tmp[1] >= next[0]) {
// 合并
vector<int> node{min(next[0],tmp[0]), max(next[1],tmp[1])};
tmp = node;
} else {
result.push_back(tmp);
tmp = next;
}
}
result.push_back(tmp);
return result;
}
总结
需要熟练掌握快速排序和二分排序.
