切一组整数范围从另一组范围 [英] Cut a set of ranges of integers from another set of ranges

问题描述

我有范围的两个数组以这种形式：

 通缉= {[10，15]，[20，25]}
切= {[5，12]，[22，24]}
 

所以希望是两个元素（范围）的阵列 - [10，15] 和 [20，25] 。

每个两阵列满足以下条件：

1. 这是由整数每个范围内第一个值排序
2. 在该范围内将不会重叠（例如 [10，15] ， [15，25] 是不可能的）
3. 这也意味着，每个范围是数组中唯一的（没有 [1,5] ， [1,5] ）
4. 如果一个范围仅仅是一个整数宽，它会显示为 [5,5] （开头和结尾都是平等的）

我现在想获得范围的数组，其中来自切断所有范围已从范围中除去希望。

 的结果= {[13，15]，[20，21]，[25，25]}
 

有一些精彩的算法更好/更容易/比下面更快？

  

对于想每个元素，该元素的比较之后，又一种元素剪切直到元素削减结束元素从上面希望。

解决方案

说，有在想 N 元素和 M 中的元素削减。

下面是一个 O（M + N）算法来完成所需的任务：

  J = 1
结果= {}
对于i = 1：N
  //进入下切而当前切入当前项目前结束
  而J＆LT; = M＆功放;＆安培;切[J] .END＆LT;希望[我]。开始
    J ++
  // cut项目后，因此没有重叠
  如果J＆GT;米||切[J]。开始＆GT;希望[我] .END
    结果+ =（想[我]。开始，希望[我] .END）
  否则//重叠
    //从开始到切断开始提取
    如果切[J]。开始＆GT;希望[我]。开始
      结果+ =（想[我]。开始，切[J]。开始-1）
    从切口处//提取结束
    如果切[J] .END＆LT;希望[我] .END
      结果+ =（切[J] .END + 1，就想[I] .END）
      J ++
 

需要注意的是，渐进，你不能这样做比 O（M + N）更好，因为它应该是相当容易证明你需要看看每个元件（在最坏的情况下）。

I have two arrays of ranges in this form:

wanted = {[10, 15], [20, 25]}
cut = {[5, 12], [22, 24]}

So wanted is an array of two elements (ranges) - [10, 15] and [20, 25].

Each of the two arrays fulfil these conditions:

1. It is sorted by the first value in each range of integers
2. The ranges will never overlap (e.g. [10, 15], [15, 25] is not possible)
3. This also means that each range is unique within the array (no [1, 5], [1, 5])
4. If a range is just one integer wide, it will be displayed as [5, 5] (beginning and end are equal)

I now want to obtain an array of ranges, where all ranges from cut have been removed from the ranges in wanted.

result = {[13, 15], [20, 21], [25, 25]}

Is there some brilliant algorithm better / easier / faster than the below?

For each element in wanted, compare that element to one element after another from cut until the element from cut ends above the element from wanted.

解决方案

Say there are n elements in wanted and m elements in cut.

The following is an O(m + n) algorithm to perform the required task:

j = 1
result = {}
for i = 1:n
  // go to next cut while current cut ends before current item
  while j <= m && cut[j].end < wanted[i].start
    j++
  // cut after item, thus no overlap
  if j > m || cut[j].start > wanted[i].end
    result += (wanted[i].start, wanted[i].end)
  else // overlap
    // extract from start to cut start
    if cut[j].start > wanted[i].start
      result += (wanted[i].start, cut[j].start-1)
    // extract from cut end to end
    if cut[j].end < wanted[i].end
      result += (cut[j].end+1, wanted[i].end)
      j++

Note that, asymptotically, you can't do better than O(m + n), since it should be reasonably easy to prove that you need to look at every element (in the worst case).

这篇关于切一组整数范围从另一组范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！