algorithm - 给定代表单个出租车预订的数据序列（开始位置，结束位置），找到最佳非中断序列

Question

我一直在尝试解决优化问题，但无法考虑任何有效的解决方案。这就是问题所在

我们得到的数据代表一辆车上的一系列预订。每个预订数据包含两个点（开始位置、结束位置）。现在给定两个相邻的预订 b1，b2，如果 b1 的结束位置不等于 b2 的开始位置，我们说这些预订之间需要重新定位

我们必须设计一种算法，该算法将预订序列作为输入，并输出输入的单个排列，以最小化序列中的重定位总数。

这是我的方法对我来说，它看起来像是一个贪婪的调度问题，但我无法从任何现有的调度问题中得出任何好的启发式方法来解决这个问题。最后，我想到了使用插入排序，根据两个相邻序列的开始时间和结束时间之间的最小差异对给定的序列进行排序。

因此，对于我们给定的问题，我们 [(23, 42),(77, 45),(42, 77)]将对其进行排序， [(23, 42),(42, 77),(77, 45)]从而最小化我的起点。

让我们再举一个例子

[(3,1),(1,3),(3,1),(2,2),(3,1),(2,3),(1,3),(1,1),(3,3),(3,2),(3,3)]

现在在使用插入排序排序到索引 7 之后，我们的数组看起来像

[ (3,1),(1,3),(3,1),(2,2),(2,3),(3,3),(3,1),(1,3) ,( 3,3),(3,2),(3,3)]

现在为了将点 (3,3) 放置在未排序数组中的索引 8 处，我们将执行以下操作

这个想法是将每个点放在正确的位置。对于索引 8 处的点 (3,3)，我将在已排序的数组中搜索其端点匹配 3 的第一个条目，即这个新点的起点，条件是在第一个找到的条目之后添加这个点不违反下一个条目的开头应该与该点的结尾匹配的变体。因此，我们在索引处的 (2,3) 和 (3,1) 之间插入 (3,3)。看起来像这样

[(3,1),(1,3),(3,1),(2,2), (2,3),(3,3),(3,1) ,(1,3),( 3,3),(3,2),(1,1)]

但是，我不确定如何证明这是最佳或非最佳解决方案。任何指针都受到高度赞赏。有没有更好的方法可以帮助我们解决这个问题。

标签： algorithmsortinggraph-algorithmschedulinggreedy

Answer 1

您可以轻松地将其转换为图形问题。

[a, b] -> 顶点 a 和 b，边在 a 和 b 之间。使用 DFS 查找此无向图中的所有连通分量并进行一些后处理。

它在输入大小上是线性的。