arrays - 从另一组范围中切出一组整数范围

Question

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

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

所以 wanted是两个元素(范围)的数组 - [10, 15]和 [20, 25] .

两个数组中的每一个都满足这些条件:

1. 按每个整数范围内的第一个值排序
2. 范围永远不会重叠(例如 [10, 15] ， [15, 25] 是不可能的)
3. 这也意味着每个范围在数组中都是唯一的(没有 [1, 5] ， [1, 5] )
4. 如果一个范围只有一个整数宽，它将显示为 [5, 5] (开始和结束是平等的)

我现在想要获取一个范围数组，其中所有范围都来自 cut已从 wanted 的范围中删除.

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

有没有比下面的算法更好/更容易/更快的算法？

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.

Answer 1

假设 wanted 中有 n 个元素，cut 中有 m 个元素。

以下是执行所需任务的O(m + n) 算法:

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++

请注意，渐近地，您不能比 O(m + n) 做得更好，因为证明您需要查看每个元素(在最坏的情况下)应该相当容易).