Write a function called sumIntervals/sum_intervals() that accepts an array of intervals, and returns the sum of all the interval lengths. Overlapping intervals should only be counted once.
Intervals
Intervals are represented by a pair of integers in the form of an array. The first value of the interval will always be less than the second value. Interval example: [1, 5] is an interval from 1 to 5. The length of this interval is 4.
Overlapping Intervals
List containing overlapping intervals:
[
[1,4],
[7, 10],
[3, 5]
]The sum of the lengths of these intervals is 7. Since [1, 4] and [3, 5] overlap, we can treat the interval as [1, 5], which has a length of 4.
Examples:
sum_intervals( {
{1,2},
{6, 10},
{11, 15}
} ); // => 9sum_intervals( {
{1,4},
{7, 10},
{3, 5}
} ); // => 7sum_intervals( {
{1,5},
{10, 20},
{1, 6},
{16, 19},
{5, 11}
} ); // => 19
我的思路是
- 创建一个limits容器存储pair
- 对输入每一条pair检查是否与limits里的pair有重叠的地方，如果有，记录下位置存入overlap
- 将limits里对应的条目删去，在重合的条目中寻找最小的下限和最大的上限，插入limits中
- 最后计算intervals
我在自己的ide中运行正常，但是在codewars提交之后在某些情况下出错，code139，是越界之类的问题。
一开始我是用vector来存储limits的，由于涉及到删除元素的问题，特意还用overlap来记录迭代器，循环之后一起删除，经过排除还是发现删除元素后迭代器失效的问题，如上第3步。于是改用list。
这次的经历更深刻的告诉我要注意迭代器失效的问题。
具体代码：
#include <vector>
#include <utility>
#include <list>
using namespace std;
int sum_intervals(std::vector<std::pair<int, int>> intervals) {
list<pair<int,int>> limits,tmp;
int tmpmin,tmpmax,res=0;
vector<list<pair<int,int>>::iterator> overlap;
if(intervals.size() == 0) return 0;
for(auto interval : intervals){
overlap.clear();
tmp.clear();
for(auto it = limits.begin();it!=limits.end();it++){
if((interval.first>=(*it).first && interval.first<(*it).second) ||
(interval.second>(*it).first && interval.second<=(*it).second) ||
(interval.first<=(*it).first && interval.second>=(*it).second)){
overlap.push_back(it);
tmp.push_back(*it);
}
}
tmp.push_back(interval);
if(overlap.size()!=0){
for(auto del_it : overlap) {limits.erase(del_it);}
tmpmin=(*tmp.begin()).first;
tmpmax=(*tmp.begin()).second;
for(auto tmp_it = tmp.begin();tmp_it!=tmp.end();tmp_it++){
if(tmpmin>(*tmp_it).first) tmpmin = (*tmp_it).first;
if(tmpmax<(*tmp_it).second) tmpmax =(*tmp_it).second;
}
limits.push_back(make_pair(tmpmin,tmpmax));
}
else limits.push_back(interval);
}
for (auto limit:limits){
res+=(limit.second-limit.first);
}
return res;
}
·提交之后，欣赏一下其他人的解答：
- 使用了set的无重复性，统计区间内的所有整数，最后返回set的size。如果数的范围大的话，浪费内存，将两个数表示的区间，生成了非常多元素的set。
#include <vector>
#include <utility>
#include <unordered_set>
int sum_intervals(std::vector<std::pair<int, int>> intervals) {
std::unordered_set<int> ints;
for (auto interv = intervals.begin(); interv != intervals.end(); ++interv){
for (int i = interv->first; i < interv->second; i++){
ints.insert(i);
}
}
return ints.size();
}
- 先进行了排序，再维护一个max_right。即可计算结果。这个答案比较好。
#include <vector>
#include <utility>
int sum_intervals(std::vector<std::pair<int, int>> interavls) {
sort(interavls.begin(), interavls.end());
int ret = 0;
int max_right = interavls[0].first;
for (auto &i : interavls)
if (i.second >= max_right) {
ret += i.second - std::max(max_right, i.first);
max_right = i.second;
}
return ret;
}
