连续相交两组区间集

Question

我们有两组间隔，A和B。

每个A中的间隔由两个正实数描述：{A1start,A1end}，{A2start,A2end}，...，{Anstart,Anend}。其中Anend始终> Anstart。 A中的间隔可能会重叠。

集合B仅由两个值描述：间隔长度和间隔距离。间隔长度是每个间隔的差值，即Bnend - Bnstart，并且> 0。间隔距离是任意两个Bnstart之间的距离。 B中的间隔可能不重叠。

我们知道在任何间隔{A1start，Anend}上，A和B中的间隔数量应该相等。

问题是：在{A1start，Anend}的间隔中，我们可以将B与A连续相交吗？即B1必须与A1相交，B2必须与A2相交等。如果除指定的间隔外，任何B与任何其他A相交都可以。

我已经制定了两个算法规则，但目前卡住了：

1. B规则允许我们计算任何{A1start，Anend}上间隔的最小和最大数量，我们用它来排除A和B中间隔数量不相等的情况。 2. 如果A中的任何间隔空隙大于B距离，则丢弃此情况，因为至少有一个B不会与任何A相交。

这两组间隔要连续相交，还需要满足哪些其他条件？

- Robert Mugattarov

---

请注意，这里没有直接的问题。你需要什么帮助？这可能会超出 SO 的主题范围（太宽泛）。 - H H

@HenkHolterman，增加了这个问题。 - Robert Mugattarov

Answer 1

你可以这样解决：

• 通过从所有Anstart值中减去长度，将A中的所有区间扩张到B的区间长度。现在，你可以认为A定义了B中区间可以开始的所有有效位置。
• 现在问题是，是否可以将一系列间隔为给定距离的点（B）与一组间隔（A）相交。你可以通过将A1与偏移量为-distance的A2、偏移量为-2distance的A3、...、偏移量为-(n-1)distance的An相交来解决这个问题。如果所有这些区间的交集非空，则A和B的交集是可能的。

- samgak

---

在额外的条件下，每个B存在的概率为P，如果没有相应的A，我们知道它不存在，那么我是否正确地假设在您的解决方案的第二步中，我可以通过B距离来削减所有A，而不是通过-(n-1)距离来抵消As，并且如果这些被削减的位相交，则集合确实相交。 - Robert Mugattarov

我不确定。如果每个B都有存在的可能性，你是在问是否保证存在交集（对于每个B组合），还是只是可能存在交集（至少一个B组合）？对于第二种情况很容易 - 只需假设它们都存在即可。对于其他情况，如果给定的B不存在，您会跳过它并留下一个空格，并跳过相应的A吗？在这种情况下，剩下的应该匹配相同。如果您不留下空格，可能会创建非交集，除非所有的A都像B距离时间A计数那样大。也许我没有正确理解您的意思。 - samgak

这是你所描述的第二种情况：如果B不存在，我们跳过相应的A并留下一个空位。问题在于，在这种情况下，我们没有应该乘以距离的因子来偏移每个A以获得交点。 - Robert Mugattarov