algorithm - 如何找到给定 N 次切割的无限杆的最大段数

Question

假设我们有一根无限长的杆，我们也有 N 段，如 [L1 , L2)。这意味着我们可以在 L1 和 L2 之前切割杆以获得一段。一些段可能会重叠。

例如给定 N=4 和

[2,3)
[1,9)
[4,5)
[5,8)

We can chose

[2,3)
[4,5)
[5,8)

segments 获取最多三个段。我不知道是否有任何众所周知的好算法？如果有的话请建议我。我可以手动完成但无法获得良好的工作算法。

Answer 1

按终点排序。

遍历片段，选择不会导致与先前片段重叠的片段(这可以通过简单地跟踪最后一个终点并检查起点是否在该点之后来检查)。

这将始终给出最佳解决方案。

对于你的例子，在排序之后，我们有:

[2,3)
[4,5)
[5,8)
[1,9)

然后我们通过 [2,3)、[4,5)、[5,8) 和 [ 1,9)，选择除 [1,9) 之外的所有项。

为什么这是最优的

显然，具有最小端点的线段将是我们的选择之一，因为与其重叠的任何线段都将具有更大的端点，因此可以与从更大值开始的更多线段重叠，并且任何线段 B 重叠具有最小端点的线段 A 也将与任何与 A 重叠的线段重叠，因此 B 不会是比 A 更好的选择。

从这里开始，我们对下一个具有不与前一个端点重叠的最小端点的线段重复此参数，直到我们到达终点。