最小化路径之间切换的算法
Algorithm to minimizing switching between paths
我有一个 l = [[1,2,3],[3,4,6],...] 形式的列表列表。有 m 个子列表，每个子列表代表一个玩家。每个玩家可以执行多项任务（有 n 个任务）。我想通过最小化玩家之间的切换次数来找到所有步骤的最短路径。所以基本上让同一个玩家尽可能多地连续执行任务。我正在尝试编写一种算法来优化它，该算法在 多项式时间 中运行，但我在想出一个好的方案时遇到了一些麻烦。我在想它可能像 Dijkstra's algorithm，但我不确定如何调整它以适合我的情况。下面是我想要的具体示例。
例子
n = 5 和 m = 3 这样我们就有一个列表列表 l = [[1,2,5],[1,3,5],[2,3,4]]
算法会 return [0,2,2,2,0]
即玩家 0 将首先被选中，然后切换到玩家 2 执行 3 个任务，而不是返回玩家 0 执行最后一个任务。
我只是在寻找伪代码或正确方向的推动。真正的挣扎和蛮力对大量的人不起作用！
由于让玩家执行的连续任务少于他所能执行的次数永远不会有好处，因此一个简单的贪心算法就足以找到最佳解决方案：
从任务 1 开始，找到从第一个任务开始可以执行最多连续任务的玩家。
从之前找到的玩家不能完成的第一个任务开始，找到从该任务开始可以执行最多连续任务的玩家。
重复直到完成所有任务。
证明这个算法是最优的：
假设有一个最佳解决方案，玩家 A 执行任务 i 到 j然后玩家 B 执行任务 j+1 到 k.
如果有任何玩家（包括A）可以执行任务i到j+1，那么我们可以使用该播放器代替执行这些任务，解决方案将是一样好或更好。任一B将执行任务j+2至k，玩家切换次数为相同，或者 j+1 = k 我们根本不需要玩家 B。
因此存在一个最佳解决方案，其中每个选定的玩家都最大化该玩家可以执行的连续移动次数。事实上，由于每个这样的解都是等价的，所以它们都是 all 最优的。
编辑：在我写这篇文章时，Pham 建议使用线段树，但不需要如此复杂的数据结构。如果子列表被排序并且你从每个任务编号到可以找到它的子列表位置建立索引，那么你可以在 O(N) 时间内完成此操作。
我有一个 l = [[1,2,3],[3,4,6],...] 形式的列表列表。有 m 个子列表，每个子列表代表一个玩家。每个玩家可以执行多项任务（有 n 个任务）。我想通过最小化玩家之间的切换次数来找到所有步骤的最短路径。所以基本上让同一个玩家尽可能多地连续执行任务。我正在尝试编写一种算法来优化它，该算法在 多项式时间 中运行，但我在想出一个好的方案时遇到了一些麻烦。我在想它可能像 Dijkstra's algorithm，但我不确定如何调整它以适合我的情况。下面是我想要的具体示例。
例子
n = 5 和 m = 3 这样我们就有一个列表列表 l = [[1,2,5],[1,3,5],[2,3,4]]
算法会 return [0,2,2,2,0]
即玩家 0 将首先被选中，然后切换到玩家 2 执行 3 个任务，而不是返回玩家 0 执行最后一个任务。
我只是在寻找伪代码或正确方向的推动。真正的挣扎和蛮力对大量的人不起作用！
由于让玩家执行的连续任务少于他所能执行的次数永远不会有好处，因此一个简单的贪心算法就足以找到最佳解决方案：
从任务 1 开始，找到从第一个任务开始可以执行最多连续任务的玩家。
从之前找到的玩家不能完成的第一个任务开始，找到从该任务开始可以执行最多连续任务的玩家。
重复直到完成所有任务。
证明这个算法是最优的：
假设有一个最佳解决方案，玩家 A 执行任务 i 到 j然后玩家 B 执行任务 j+1 到 k.
如果有任何玩家（包括A）可以执行任务i到j+1，那么我们可以使用该播放器代替执行这些任务，解决方案将是一样好或更好。任一B将执行任务j+2至k，玩家切换次数为相同，或者 j+1 = k 我们根本不需要玩家 B。
因此存在一个最佳解决方案，其中每个选定的玩家都最大化该玩家可以执行的连续移动次数。事实上，由于每个这样的解都是等价的，所以它们都是 all 最优的。
编辑：在我写这篇文章时，Pham 建议使用线段树，但不需要如此复杂的数据结构。如果子列表被排序并且你从每个任务编号到可以找到它的子列表位置建立索引，那么你可以在 O(N) 时间内完成此操作。