减数范围算法

Question

如何完成以下操作:取一个范围数组并从中减去另一个范围数组。

例如：

arr0 = [[0,50],[60,80],[100,150]] # 0-50, 60-80, etc.

arr1 = [[4,8],[15,20]] # 4-8, 15-20, etc.

# arr0 - arr1 magic

result = [[0,3],[9,14],[21,50],[60,80],[100,150]] # 0-3, 9-14, etc.

在Ruby中，最干净和最有效的方法是什么？

Answer 1

这是一个刻意幼稚的解决办法。它效率不高，但容易理解，而且很短。

将arr0解构成一个数列：

n1 = arr0.flat_map { |a, b| (a..b).to_a }
#=> [0, 1, ..., 49, 50, 60, 61, ..., 79, 80, 100, 101, ..., 149, 150]

同样适用于arr1

n2 = arr1.flat_map { |a, b| (a..b).to_a }
#=> [4, 5, 6, 7, 8, 15, 16, 17, 18, 19, 20]

然后，从n2中减去n1并重新组合连续数字：

(n1 - n2).chunk_while { |a, b| a.succ == b }.map(&:minmax)
#=> [[0, 3], [9, 14], [21, 50], [60, 80], [100, 150]]