查找最长非重叠序列的算法

Question

我正在尝试找到解决以下问题的最佳方法。我所说的最好的方式是不那么复杂。

作为输入的元组列表(开始，长度)如下:

[(0,5),(0,1),(1,9),(5,5),(5,7),(10,1)]

每个元素通过它的开始和长度来表示一个序列，例如(5,7)等价于序列(5,6,7, 8,9,10,11) - 以 5 开头的 7 个元素的列表。可以假设元组按 start 元素排序。

输出应返回表示最长连续序列的非重叠元组组合。这意味着，一个解决方案是范围的子集，没有重叠，没有间隙，并且是最长的可能 - 虽然可能不止一个。

例如对于给定的输入，解决方案是:

[(0,5),(5,7)] 相当于 (0,1,2,3,4,5,6,7,8,9,10 ,11)

回溯是解决这个问题的最佳方法吗？

我对人们可以建议的任何不同方法感兴趣。

此外，如果有人知道这个问题或另一个类似问题的正式引用，我想获得引用。

顺便说一句 - 这不是家庭作业。

编辑

为了避免一些错误，这是预期行为的另一个例子

对于像 [(0,1),(1,7),(3,20),(8,5)] 这样的输入，正确的答案是 [(3, 20)] 等同于长度为 20 的 (3,4,5,..,22)。收到的一些答案会给出 [(0,1),(1,7),(8 ,5)] 相当于 (0,1,2,...,11,12) 作为正确答案。但是最后一个答案是不正确的，因为它比 [(3,20)] 短。

Answer 1

使用给定的顺序(按开始元素)迭代元组列表，同时使用 HashMap 跟踪特定索引上结束的最长连续序列的长度。

伪代码，跳过 HashMap 中未找到的项目等详细信息(假设未找到则返回 0):

int bestEnd = 0;
hashmap<int,int> seq // seq[key] = length of the longest sequence ending on key-1, or 0 if not found
foreach (tuple in orderedTuples) {
    int seqLength = seq[tuple.start] + tuple.length
    int tupleEnd = tuple.start+tuple.length;
    seq[tupleEnd] = max(seq[tupleEnd], seqLength)
    if (seqLength > seq[bestEnd]) bestEnd = tupleEnd
}
return new tuple(bestEnd-seq[bestEnd], seq[bestEnd])

这是一个 O(N) 算法。

如果您需要组成这个序列的实际元组，您还需要保留一个按结束索引散列的元组链接列表，每当为该结束点更新最大长度时更新它。

更新:我对 python 的了解相当有限，但根据您粘贴的 python 代码，我创建了这段返回实际序列而不仅仅是长度的代码:

def get_longest(arr):
    bestEnd = 0;
    seqLengths = dict() #seqLengths[key] = length of the longest sequence ending on key-1, or 0 if not found
    seqTuples = dict() #seqTuples[key] = the last tuple used in this longest sequence
    for t in arr:
        seqLength = seqLengths.get(t[0],0) + t[1]
        tupleEnd = t[0] + t[1]
        if (seqLength > seqLengths.get(tupleEnd,0)):
            seqLengths[tupleEnd] = seqLength
            seqTuples[tupleEnd] = t
            if seqLength > seqLengths.get(bestEnd,0):
                bestEnd = tupleEnd
    longestSeq = []
    while (bestEnd in seqTuples):
        longestSeq.append(seqTuples[bestEnd])
        bestEnd -= seqTuples[bestEnd][1]
    longestSeq.reverse()
    return longestSeq


if __name__ == "__main__":
    a = [(0,3),(1,4),(1,1),(1,8),(5,2),(5,5),(5,6),(10,2)]
    print(get_longest(a))