algorithm - 找到与所有弧线相交的最小射线数

Question

Elements of Programming Interviews 中有一个问题我曾尝试解决但未成功。假设我们得到一个 (d1, d2) 形式的间隔数组，其中 d1 和 d2 是表示开始和结束的以度为单位的值弧的角度，其中 0 度是 y 轴。这些间隔可以重叠，您可以有一个像 (350, 10) 这样的间隔。您可以射出与所有间隔相交的最少光线数是多少？一条射线可以表示为与 y 轴的角度。

我已经尝试按端点排序并查看每个端点是否与下一个间隔相交，但我无法弄清楚如何处理重叠间隔，例如 (340, 350), (350, 20 )。

Answer 1

为了优化弧的数量，例如，如果 A 和 C 相交，您不能将一条射线从 A 转换到 B，将另一条射线从 C 转换到 D。

关键是找到所有圆弧之间的交点(并按属于更多圆弧的点排序)。

对它们进行排序后，获取属于更多弧的角度，并设置从它到属于不同于第一组的其他弧组的另一个点的射线。最不同，更好。您可以移动角度并检查最适合的角度。