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.
A simple way to calculate the distance between numbers on a number line is to count every number between them. A faster way is to find the distance by taking the absolute value of the difference of those numbers. For example, the absolute values of 4 and -4, or |4| and |-4|, are both 4.
Approach: The task is to find the distance between two given numbers, So find the distance between any two elements using nested loops. The outer loop for selecting the first element (x) and the inner loop for traversing the array in search for the other element (y) and taking the minimum distance between them.
1) Sort all intervals in increasing order of start time. This step takes O(nLogn) time. 2) In the sorted array, if start time of an interval is less than end of previous interval, then there is an overlap.
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With