What is the algorithm for two intervals difference?

1
votes

I'm making a program in Python where I have 2 intervals as an input and then it has to return 3 operations: - union (A | B) - intersection (A & B) - difference

I've tried making sets for intervals A and B and then subtract them with set method (A-B) but it has no sense as it has to return an interval, not a set and I distinguish between open / closed / open_closed etc intervals.

input: [3, 10) (5, 16]

output: Difference A\B: [3,5] Difference B\A: [10, 16]

3
pythonalgorithmintervals
What happens if one interval is fully contained in the other, as in, subtracting [3, 4] from [1, 7]? How should the result be expressed? - templatetypedef
then it it [1,3) ∪ (4,7] However, [1,7] subtract from [3,4] would return null - laczka

3 Answers

1
votes

Let's represent an Interval I with the following data

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

Note also that

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

Now take two intervals A = {a1, a2} and B = {b1, b2}. We have

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

with

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

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

Note that this reduces the problem to compute two intersections, which you can do with generality. However, for the sake of completeness, let's work the details here:

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

and

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

Since the difference can be reduced to the union of two intersections it's worth resolving the intersection in the general case, between two intervals A = {a1, a2} and 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
0
votes

Have you tried populating your set representations of the intervals and then applying set operations? For example:

interval [3,10) -> set(3,4,5,6,7,8,9)

interval (5,16] -> set(6,7,8,9,10,11,12,13,14,15,16)

Perhaps range would be helpful in the gap-filling part.

0
votes

I did not fully understand your question. But try this, hope this is what you're looking for :

A = set(range(3,10)) # {3, 4, 5, 6, 7, 8, 9}
B = set(range(6,17)) # {6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}

u = A.union(B) # {3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16}
v = A.intersection(B) # {6, 7, 8, 9}
x = A.difference(B) # {3, 4, 5}
y = B.difference(A) # {10, 11, 12, 13, 14, 15, 16}