在两个区间之间寻找整数距离

Question

我正在寻找一种使用Python查找两个整数区间之间最小距离的简单方法。例如，[0,10]和[12,20]之间的最小距离是2。如果两个区间有任何重叠，距离将为0。

您有关于简单实现的建议吗？我认为必须有一种干净的、符合Python风格的方法来解决这个问题。

- David M

Answer 1

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

---

+1。这个答案似乎很有效。我显然太累了，无法在脑海中理清这个问题 >.> - Gareth Latty

我不是很清楚 * 运算符对 args 做了什么，以及 sorted() 如何在这两个列表上工作 - 你能解释一下吗？ - David M

在函数参数的上下文中，“*”用于将参数值放入列表中。通常用于可变数量的参数，但此处我们已经使用了列表，因此可以使用它来节省一行代码。 x，y = sorted（args）将扩展列表到两个变量x和y。这样做的目的是确保x小于y。 - krs

运行以下代码会失败，因为区间的顺序是无序的： print solve((2,10), (11,8)) # 返回 1 - Kostanos

(11, 8) 可以被解释为一个有效的空区间。 - jfs

Answer 2

希望以下内容能够帮到您：

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

祝你好运!!!

- Nate Kingsley

Answer 3

dist=min(y)-max(x)
if dist>0:
    return dist
else:
    return 0

- Wesley Bowman

Answer 4

并不真正依赖于编程语言：

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

（这里假设区间是闭合的。如果区间是开放的，您需要相应地调整检查不良区间的方法。）

---

其他答案缺乏其公式的解释，让我来解释一下：

设两个区间为 [startA, endA] 和 [startB, endB]。当且仅当以下条件成立时，这两个区间有重叠：

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

由于我们只关心没有重叠的情况，因此我们取反该条件

(StartA > EndB) or (StartB > EndA)

现在如果 StartA > EndB，那么第一个区间在第二个区间的右侧，它们之间的距离是 startA - endB。反之，如果 StartB > EndA，第一个区间在第二个区间的左侧，它们之间的距离是 startB - endA。

将其结合起来，我们得到

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

现在考虑以下情况：(a) 对于有效的区间（即EndA >= StartA和EndB >= StartB），如果没有重叠部分，则StartA - EndB或StartB - EndA中的任意一个将为负数^*，(b) 对于重叠的范围，StartA - EndB和StartB - EndA都将是非正数^**。然后你可以简化为：

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

至于无效的区间：如果一个区间是无效的，并且我们定义它为空区间，即一个没有任何元素的空集合，我们进一步定义两个区间之间的距离为可以添加的最小区间的长度，以便它与两个区间形成一个单一连续区间，那么无效区间和另一个区间之间的距离为0（因为第二个区间已经形成了一个单一连续区间，所以我们只需要添加一个长度为0的空区间）。

---

(*) 如果例如第一个间隔在第二个间隔的右边，那么就会得出：

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

(**) 由于对于重叠的范围，我们有 StartA <= EndB 和 StartB <= EndA，因此可以得出 StartA - EndB <= 0 和 StartB - EndA <= 0

- blutorange