合并重叠的跨度/范围

本文介绍了合并重叠的跨度/范围的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 我写的是免费查找时间。日历功能。有很多 的时间跨度有开始结束时间，有些重叠，有些则没有。 要查找空闲时间跨度，我首先需要转换将事件转换为 非重叠时间跨度列表meta-span。 这个漂亮的ascii图应该显示我的意思。 1）--- 2）--- 3）--- 4） ----- 5）----- I am writing a "find-free-time" function for a calendar. There are a lotof time spans with start end times, some overlapping, some not. To find the free time spans, I first need to convert the events into alist of non overlapping time spans "meta-spans". This nice ascii graph should show what I mean. 1) ---2) ---3) ---4) -----5) ----- """ 类MetaSpans： """ 填充span元组列表[（开始，结束）]，它将使 " meta" 跨度，重叠跨度折叠成一个跨度。 " " def __init __（自我）： self.spans = [] def add （self，span）： start，end = span 重叠= [span] non_overlapping = [] $ b self.spans中spn的$ b： spn_start，spn_end = spn ＃跨越跨度的跨度规则 starts_before = spn_start< =开始 ends_after = spn_end> =结束 is_outside = starts_before和ends_after starts_inside = start< = spn_start< = end ends_inside = start< = spn_end< = end overlapps = starts_inside或ends_inside or is _outside 如果重叠： overlap.append（spn） else： non_overlapping.append（spn） ＃重叠跨度改为一个跨度 starts = [] ends = [] 开始，以重叠结束： starts.append（开始） ends.append（结束） min_start = min（开始） max_end = max（结束） non_overlapping.append（（min_start，max_end）） self.spans = non_overlapping def findFreeTime（self，duration）： self.spans.sort（） if __name__ ==''__ main __''： ms = MetaSpans（） ms.add（（0,3）） ms.add（（4,7） ）） ms.add（（2,5）） ms.add（（9,14）） ms.add（ （12,17）） 打印ms.spans 从日期时间导入日期时间 ms = MetaSpans（） ms.add（（datetime（2005,1,1,0,0,0），datetime（2005,1,1,3,0,0））） ms.add（（ datetime（2005年，1 ，1，4，0，0），datetime（2005,1,1,7,0,0））） ms.add（（datetime（2005,1,1,2,0） ，0），datetime（2005,1,1,5,0,0））） ms.add（（datetime（2005,1,1,9,0,0），datetime（ 2005,1,1,14,0,0））） ms.add（（datetime（2005,1,1,12,0,0），datetime（2005,1,1， 17,10， 0））） 打印ms.spans - hilsen / respect Max M，Denmark http：// www.mxm.dk/ IT的疯狂科学 """ class MetaSpans: """Populate with a list of span tuples [(start,end)], and it will make"meta"spans, with overlapping spans folded into one span.""" def __init__(self):self.spans = [] def add(self, span):start, end = spanoverlapping = [span]non_overlapping = []for spn in self.spans:spn_start, spn_end = spn# span rules for iterated spansstarts_before = spn_start <= startends_after = spn_end >= endis_outside = starts_before and ends_afterstarts_inside = start <= spn_start <= endends_inside = start <= spn_end <= endoverlaps = starts_inside or ends_inside or is_outsideif overlaps:overlapping.append(spn)else:non_overlapping.append(spn)# overlapping spans are changed to one spanstarts = []ends = []for start, end in overlapping:starts.append(start)ends.append(end)min_start = min(starts)max_end = max(ends)non_overlapping.append( (min_start, max_end) )self.spans = non_overlappingdef findFreeTime(self, duration):self.spans.sort() if __name__ == ''__main__'': ms = MetaSpans()ms.add((0,3))ms.add((4,7))ms.add((2,5))ms.add((9,14))ms.add((12,17))print ms.spansfrom datetime import datetimems = MetaSpans()ms.add((datetime(2005, 1, 1, 0, 0, 0), datetime(2005, 1, 1, 3, 0, 0)))ms.add((datetime(2005, 1, 1, 4, 0, 0), datetime(2005, 1, 1, 7, 0, 0)))ms.add((datetime(2005, 1, 1, 2, 0, 0), datetime(2005, 1, 1, 5, 0, 0)))ms.add((datetime(2005, 1, 1, 9, 0, 0), datetime(2005, 1, 1, 14, 0, 0)))ms.add((datetime(2005, 1, 1, 12, 0, 0), datetime(2005, 1, 1, 17, 0,0)))print ms.spans -- hilsen/regards Max M, Denmark http://www.mxm.dk/IT''s Mad Science推荐答案 我认为以下代码可以满足您的需求。它应该是O（n log n） - 至少我希望Python能够对字符串列表进行排序:) 当然我已经假设你了您可以一次性使用这些空间 作为列表，并且不需要像在 原始代码中那样一次添加一个。 def get_metaspans（spans）： """给定一个span元组列表[（start，end）]，将生成所有 元跨度，重叠跨度折叠成一个跨度。 "" spans.sort（） spans = iter（spans） metaspan = spans.next（）跨度跨度： start，end = span m_start，m_end = metaspan 如果开始> m_end： 收益分数 metaspan = span elif end> m_end： metaspan =（m_start，end） ＃一旦跨度列表耗尽，需要产生最终的metaspan yield metaspan def get_breaks（metaspans）： """获取metaspans序列之间的所有间隔""" metaspans = iter（metaspans） _，prev_end = metaspans.next（）元数据中metaspan的： start，end = metaspan 收益率（prev_end，start） prev_end =结束 我必须承认我有点生气勃勃，我会倾向于在任何给定的机会下抛出收益 :)最后不得不再次收益 的get_metaspans循环似乎有点不优雅，也许它可能会更好地完成。但它很好处理空列表的方式 优雅 - .next（）调用抛出的StopIteration只是 吸收了，呃，生成器。 一点点测试： I think the following code does what you want. It should be O(n log n)- at least I hope thats what Python takes to sort the list of spans :)Of course I''ve assumed you have the spans available to you all at onceas a list, and dont need to add them one at a time as you did in youroriginal code. def get_metaspans(spans):"""Given a list of span tuples [(start,end)], will generate allmeta spans, with overlapping spans folded into one span."""spans.sort()spans = iter(spans)metaspan = spans.next()for span in spans:start, end = spanm_start, m_end = metaspanif start > m_end:yield metaspanmetaspan = spanelif end > m_end:metaspan = (m_start, end)# Need to yield the final metaspan once the span list is exhaustedyield metaspan def get_breaks(metaspans):"""Gets all the breaks in between a sequence of metaspans"""metaspans = iter(metaspans)_, prev_end = metaspans.next()for metaspan in metaspans:start, end = metaspanyield (prev_end, start)prev_end = end I must admit I''m a bit of a generatoraholic, I''ll tend to throw yieldsat anything given half a chance :) Having to yield once more at the endof the get_metaspans loop seems a little inelegant, maybe it could bedone a bit better. But its nice the way empty lists are handledgracefully - the StopIteration thrown by the .next() calls are justabsorbed by the, uh, generatorness. A little bit of testing: [（6,8） ，（10,12）] 这或多或少是需要的吗？ [(6, 8), (10, 12)] Is that more or less what was required? 这篇关于合并重叠的跨度/范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！