python - 两个间隔差的算法是什么？

Question

我正在用 Python 编写一个程序，其中我有 2 个间隔作为输入，然后它必须返回 3 个操作:- 联盟 (A | B)- 交叉路口(A 和 B)- 区别

我已经尝试为间隔 A 和 B 设置集合，然后使用 set 方法 (A-B) 减去它们，但它没有任何意义，因为它必须返回一个间隔，而不是一个集合，我区分 open/closed/open_closed 等间隔。

输入:[3, 10)(5, 16]

输出:差异 A\B:[3,5]差异 B\A: [10, 16]

Answer 1

让我们用以下数据表示一个区间 I

{i, j}  "the limits" with
I.left = I.includes(i)
I.right = I.includes(j)

还要注意

I.isEmpty = (i > j) | (i = j) & (I.left.not | I.right.not)

现在取两个区间 A = {a1, a2} 和 B = {b1, b2}。我们有

A - B = A & (-inf, b1} | A & {b2, +inf)

与

(-inf, b1}.left = false
(-inf, b1}.right = B.left.not

{b2, +inf).left = B.right.not
{b2, +inf).right = false.

请注意，这减少了计算两个交点的问题，您可以通过泛化来做到这一点。然而，为了完整起见，让我们在这里处理细节:

A & (-inf, b1} = {a1, min(a2, b1)} with
(A & (-inf, b1}).left = A.left
(A & (-inf, b1}).right = 
                         if(a2 < b1) A.right
                         elseif(a2 = b1) A.right & B.left.not
                         else B.left.not

和

A & {b2, +inf) = {max(a1, b2), a2} with
(A & {b2, +inf)).left = 
                        if(a1 < b2) B.right.not
                        elseif(a1 = b2) A.left & B.right.not
                        else A.left
(A & {b2, +inf)).right = A.right

---

由于差异可以减少为两个交集的并集，因此在一般情况下，在两个区间 A = {a1, a2} 和 B = {b1 之间解决交集是值得的, b2}.

A & B = {max(a1, b1), min(a2, b2)} with
(A & B).left = if(a1 < b1) B.left elseif(a1 = b1) A.left & B.left else A.left
(A & B). right = if(a2 < b2) A.right elseif(a2 = b2) A.right & B.right else B.right