提问人：Matic 提问时间：11/13/2023 更新时间：11/13/2023 访问量：46
间隔重叠 - 落球问题
Interval overlapping - falling ball problem
问：
我正在研究一个与间隔重叠算法相关的问题。简短的描述是：
我们有一个 2D 网格，我们可以在每次循环迭代中放置/移除木板。当我们从顶部掉落一个球时（S 位置可以是随机的），我需要确定它可以掉到的最深位置。
我已经尝试了经典的间隔重叠算法，但我几乎可以肯定我真的可以使它更优化。我试过从顶部绕过 V 轴，并检查摇杆间隔是否重叠，以便覆盖整个“孔”。
我首先看到的一项优化是，我可以跟踪最小 V 位置并在此处开始循环。
我还得到了一个提示，我应该使用最佳数据结构，这将“允许我按每列的 Y 坐标对棒进行排序”。我不确定按 Y 排序对我有什么帮助——我错过了什么吗？
此外，我一直在阅读一些算法，它认为分段树也可以解决这个问题。尝试这种方法是否可行，或者我只是在这里在黑暗中拍摄？
答：
0赞
Aldert
11/20/2023
#1
我根据您的问题制作了以下示例。我只取了你的实线，并称它们为段。
S1 (0,4) Y2
S2 (1,3) Y5
S3 (4,8) Y7
S4 (8,10) Y6
您可以按如下方式创建区段树：
S=5： 从根节点向下移动到叶子。在根节点 5 < 9 = true，所以我们向左转，下一个节点 5 < 8 = false，所以我们向右转。我们还将 s1 记录为找到的段。下一个节点 5 < 4 = false，我们再次向右走，我们在叶子 4 处找到 s3。 所以我们有 2 行，我们必须检查端点是否为 >= 5，只有 s3 是这种情况。Y = 7 是答案。
S=8：8 < 8 = false，向右转。我们发现 s4， 8 < 10 = true，向左走。我们发现叶子 8 和 S3。我们让 S3 和 S4 检查终端节点是否 >= 8，因为两者都是真的。我们发现 Y= 6 为最小 Y。
上一个：深度优先搜索逻辑递归函数
评论