algorithm - 给定两个范围 [a,b), [c,d)，检查它们是否相交

Question

我从 cscareerquestions 中找到的 Google 电话面试问题是

Given two ranges [a,b), [c,d), check if they intersect.

http://www.reddit.com/r/cscareerquestions/comments/2xrzst/just_got_rejected_from_google_after_my_phone/

受访者说:

I just worked out the midpoints and the radii of the two ranges. Then checked if the difference in the midpoints were smaller than the radii summed.

The interviewer mentioned two things. When taking the difference, what if one is smaller than the other. I said, just check and make sure you do it the right way round. About 10 minutes after the call, I realised I could've just used the absolute value of the difference instead. Then he mentioned that the [) notation means inclusive, so you don't include the last value. So I just decremented the end of each range.

解决这个问题的好方法是什么？有人会用例子解释吗？

Answer 1

这是课本答案:

如果两个范围不相交，则其中一个完全位于另一个范围的左侧，也就是说:b≤c 或 d≤a。比较是 ≤ 因为范围是半开的；例如，如果 b=c，则范围不相交，因为 b 不在 [a 中， b)。

因此，如果上述情况不成立，则范围相交:

不(b≤c 或 d≤a ) ≡ 不 b≤c 和 不 d≤a ≡ bc 和 d>< em>a

---

那么现实生活中的编程呢？除了上述情况，还有一种情况是两个范围不相交:当其中一个或两个为空时。

这很重要，因为空范围往往会出现，而且它们可能有任意端点。您当然不想报告 [0,2) 和 [1,1) 相交，因为它们不相交，这可能是一个重要的错误。

那么让我们问一个不同的问题:两个范围的交集是多少？答案很简单:交集的左侧边缘是两个范围左侧边缘中较大的一个，右侧边缘是右侧边缘中较小的一个。数学上:

[a,b)∩[c,d) ≡ [ ma​​x(a, c),min(b,d))

由于如果半开范围的右边缘小于或等于其左边缘，则半开范围为空，我们可以产生更具弹性的定义:

范围相交 [a,b), [ c,d) ≡ min(b,d) > 最大(a,c)