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

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)]相当于(3,4,5,...,22)长度为20.收到的一些答案[(0,1),(1,7),(8,5)]相当于(0,1,2,...,11,12)作为正确答案.但这最后的答案是不正确的,因为它比短于[(3,20)].

Answer 1

使用给定的排序(通过start元素)迭代元组列表,同时使用散列映射来跟踪以某个索引结尾的最长连续序列的长度.

伪代码,跳过详细信息,例如在散列映射中找不到的项目(如果未找到,则返回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))