CodeWar::Sum of Intervals

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}
} ); // => 9

sum_intervals( {
{1,4},
{7, 10},
{3, 5}
} ); // => 7

sum_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;
}

CodeWar::Sum of Intervals

推荐阅读更多精彩内容