5

I'm looking for an easy way to find the minimum distance between two integer intervals using python. For example, the minimum between [0,10] and [12,20] would be 2. If the two intervals overlap in any way, the distance would be 0.

Any suggestions on an easy way to do this? I can't help but think there must be a clean, 'pythonic' way to get at this question.

George Cummins
  • 28,485
  • 8
  • 71
  • 90
David M
  • 710
  • 1
  • 8
  • 14

4 Answers4

6
def solve(r1, r2):
     # sort the two ranges such that the range with smaller first element
     # is assigned to x and the bigger one is assigned to y
     x, y = sorted((r1, r2))

     #now if x[1] lies between x[0] and y[0](x[1] != y[0] but can be equal to x[0])
     #then the ranges are not overlapping and return the differnce of y[0] and x[1]
     #otherwise return 0 
     if x[0] <= x[1] < y[0] and all( y[0] <= y[1] for y in (r1,r2)):
        return y[0] - x[1]
     return 0
... 
>>> solve([0,10],[12,20])
2
>>> solve([5,10],[1,5])
0
>>> solve([5,10],[1,4])
1
Ashwini Chaudhary
  • 244,495
  • 58
  • 464
  • 504
  • 1
    +1. This answer appears to work well. I'm apparently to tired to get this one straight in my head >.> – Gareth Latty May 30 '13 at 18:45
  • I'm not really clear on what the * operator is doing to args, and how sorted() works on the two lists - could you explain that a bit? – David M May 30 '13 at 18:52
  • * in the context of function parameters is used to place the parameter values in a list, its usually used for a variable amount of parameters but here we then in a list anyway so can use that to save a row of code. the x,y = sorted(args) will expand the list to the two variables x and y. Its all to make sure that x is less then y – krs May 30 '13 at 18:55
  • @DavidM I've added some explanation. – Ashwini Chaudhary May 30 '13 at 19:16
  • it will fails with unordered intervals: print solve((2,10), (11,8)) # return 1 – Kostanos May 30 '13 at 19:31
  • @Kostanos well mathematically in an [interval](https://en.wikipedia.org/wiki/Interval_(mathematics)) (a,b), a<=b. So `(2,10), (11,8)` is an invalid input here. But this can be handled easily if we sort the ranges first. – Ashwini Chaudhary May 30 '13 at 20:38
  • `(11, 8)` can be interpreted as a valid *empty* interval. – jfs May 30 '13 at 20:57
0
dist=min(y)-max(x)
if dist>0:
    return dist
else:
    return 0
Wesley Bowman
  • 1,366
  • 16
  • 35
0

Hopefully the following helps:

def myDist(a,b):
    if a[0] <= a[1] < b[0]:
        return b[0] - a[1]
    if b[0] <= b[1] < a[0]:
        return a[0] - b[1]
    return 0

Good Luck!!!

Nate Kingsley
  • 1
0

Doesn't really depend on the programming language:

if (EndA < StartA || EndB < StartA) # check for malformed intervals
  return 0;
return max(0, StartA - EndB, StartB - EndA)

(This assumes the intervals are closed. If the intervals are open, you need to adjust the check for malformed intervals accordingly.)

The other answers lack justification for their formulas, so let me give one:

Let the two intervals be [startA, endA] and [startB, endB]. The two intervals overlap if

(StartA <= EndB) and (StartB <= EndA)

Since we are only interested in the case where there is no overlap, we take the negation of that condition

(StartA > EndB) or (StartB > EndA)

Now if StartA > EndB, then the first interval lies to the right of the first, so their distance is startA - endB. Conversely, if StartB > EndA, the first lies to the left of the second, so their distance is startB - endA.

Taken together we get

if (StartA > EndB):
  return StartA - EndB
if (StartB > EndA):
  return StartB - EndA
return 0

Now consider that (a) for valid intervals (i.e. EndA >= StartA and EndB >= StartB), either one of StartA - EndB or StartB - EndA will be negative if there is no overlap*, and that (b) for overlapping ranges both StartA - EndB and StartB - EndA will be non-positive**. Then you can shorten this to:

max(0, StartA - EndB, StartB - EndA)

As for invalid intervals: If an interval is invalid and we define that to mean an empty interval, i.e. as an empty set without any elements, and we further define the distance between two intervals as the length of the smallest interval that can be added so that it together with both intervals forms a single continuous interval, then the distance between an invalid interval and another interval is 0 (as the second interval already forms a single continuous interval, so we only need to add an empty interval, which has length 0).

(*) If e.g. the first interval lies to the right of the second, it follows that

StartA > EndB // assuming first interval lies to the right of the second
EndA >= StartA // assuming first interval is valid
EndB >= StartB // assuming first interval is valid

EndA >= StartA > EndB >= StartB // combine the inequalities
EndA > StartB // shorten
StartB - EndA < 0 // so the other quantity is negative

(**) Since for overlapping ranges we have StartA <= EndB and StartB <= EndA, it follows that StartA - EndB <= 0 and StartB - EndA <= 0

blutorange
  • 320
  • 3
  • 14