algorithm - 连续相交两组区间

Question

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

A 中的每个区间都由两个正实数 {A1start,A1end},{A2start,A2end},...,{Anstart,Anend} 描述。 Anend 总是 > Anstart。 A MAY 中的间隔重叠。

集合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 相交。

这两个集合连续相交还必须满足哪些其他条件？

Answer 1

你可以这样解决:

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