<p>假设范围按下界排序,我们希望将当前范围附加到它可以附加到的最长路径上,或者创建一个新路径(附加到空路径)。如果需要的话,我们可以考虑让搜索最长前缀的效率更高。(下面的代码只是用稍微优化的线性方法更新搜索。)</p>
<p>(我不知道如何使用yield功能,也许您可以让这段代码更优雅。)</p>
<pre class="lang-py prettyprint-override"><code># Assumes spans are sorted by lower bound
# and each tuple is a valid range
def f(spans):
# Append the current span to the longest
# paths it can be appended to.
paths = [[spans.pop(0)]]
for l,r in spans:
to_extend = []
longest = 0
print "\nCandidate: %s" % ((l,r),)
for path in paths:
lp, rp = path[-1]
print "Testing on %s" % ((lp,rp),)
if lp <= l < rp:
prefix = path[:-1]
if len(prefix) >= longest:
to_extend.append(prefix + [(l,r)])
longest = len(prefix)
# Otherwise, it's after so append it.
else:
print "Appending to path: %s" % path
path.append((l, r))
longest = len(path)
for path in to_extend:
print "Candidate extensions: %s" % to_extend
if len(path) == longest + 1:
print "Adding to total paths: %s" % path
paths.append(path)
print "\nResult: %s" % paths
return paths
all_spans = [(0, 5), (2, 7), (5, 8), (6, 10), (9, 10), (11, 15)]
f(all_spans)
</code></pre>
<p>输出:</p>
^{pr2}$