合并区间问题

本题是Leetcode的56题Merge Intervals,主要来训练排序的

Description

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

分析

本周想对排序进行练习,上周的Kth最大子数组就是用归并排序来完成的,是训练分治也是训练排序。本周从sort标签中选了第一题。
首先需要将各个区间按第一个起始位置排序,然后去合并这些区间即可。这里采用的是快速排序的方式,而且合并的过程也采用与快排查找中间位置类似的想法。
这书写上,想着用一下函数范式的一些规则,形参不改变,返回一个相同的参数,使函数无状态。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {

vector<Interval> sortedVals = sortInterval(intervals);
vector<Interval> mergedVals = mergeInterval(sortedVals);

return mergedVals;
}

vector<Interval> sortInterval(vector<Interval> &intervals){
vector<Interval> sortedVals = intervals;
quickSortInterval(sortedVals, 0, sortedVals.size()-1);

return sortedVals;
}

void quickSortInterval(vector<Interval> &intervals, int start, int end){

if(start >= end){
return;
}

int mid = partition(intervals, start, end);
quickSortInterval(intervals, start, mid-1);
quickSortInterval(intervals, mid+1, end);
}

int partition(vector<Interval> &intervals, int start, int end){
Interval ref = intervals[end];

int i = start-1;
for(int j=start; j<end; ++j){
if(intervals[j].start < ref.start){
i++;

exchange(intervals[i], intervals[j]);
}
}

int mid = i+1;
exchange(intervals[mid], intervals[end]);
return mid;
}

void exchange(Interval &a, Interval &b){
Interval tmp = a;
a = b;
b = tmp;
}


vector<Interval> mergeInterval(vector<Interval> &intervals){
int len = intervals.size();
if(len <= 1){
return intervals;
}

vector<Interval> mergedVals;
int j = 0;

for(int i=j+1; i<len; ++i){
if(intervals[j].end < intervals[i].start){
mergedVals.push_back(intervals[j]);
j=i;
} else if(intervals[j].end < intervals[i].end){
intervals[j].end = intervals[i].end;
}

if(i == len-1){
mergedVals.push_back(intervals[j]);
}
}

return mergedVals;
}
};

总结

本题在合并区间的时候考虑过将合并掉的区间删除,考虑到vector删除size发生变化,就思考与快排用两个指示器来处理的方式。这种方式其实改变了传入值,其实可以做一层复制来规避,这里图简单,没有将无状态贯彻到底。