我想输入间隔列表，并检查重叠间隔和非重叠间隔的并集间隔 [英] I want to input a list of intervals and check the intervals of the union of overlapping intervals and the intervals of non-overlapping intervals

问题描述

例如:我有 intervals = [[-5，-3]，[-4，-1]，[1,3]，[4,8]，[5,10]，[10,12]，[15,20]] (不必那样排序)

For example: I have the intervals = [[-5,-3],[-4,-1],[1,3],[4,8],[5,10],[10,12], [15,20]] (not necessaraly sorted like that)

我希望函数返回我 [[-5，-1]，[1,3]，[4,12]，[15,20]] .由于 [-5，-3]，[-4，-1]和[4,8]，[5,10]，[10,12] 具有互相交叉的数字.即，我希望函数返回所有寂寞的"消息.时间间隔，以及它们的数字彼此相交的时间间隔的并集的最小值和最大值.

I want the function to return me [[-5,-1],[1,3],[4,12],[15,20]]. Since [-5,-3],[-4,-1] and [4,8],[5,10],[10,12] have numbers that intercept each other. I.e., I want the function to return all the "lonely" intervals and the min's and max's of the union of the intervals in which their numbers intercept each other.

我有这段代码可以做类似的事情，但这不是我想要的:

I have this code that do something similar, but it isn't what I want yet:

def maxDisjointIntervals(list_): 
      
    # Lambda function to sort the list   
    # elements by second element of pairs  
    list_.sort(key = lambda x: x[1]) 
      
    # First interval will always be  
    # included in set  
    print("[", list_[0][0], ", ", list_[0][1], "]") 
      
    # End point of first interval 
    r1 = list_[0][1] 
      
    for i in range(1, len(list_)): 
        l1 = list_[i][0] 
        r2 = list_[i][1] 
          
        # Check if given interval overlap with  
        # previously included interval, if not  
        # then include this interval and update  
        # the end point of last added interval 
        if l1 > r1: 
            print("[", l1, ", ", r2, "]") 
            r1 = r2 

此代码向我返回此输出: [[-5，-3]，[1，3]，[4，8]，[10，12]，[15，20]]

This code is returning me this output: [[-5, -3],[1, 3],[4, 8],[10, 12],[15, 20]]

重复我之前说的话:我希望它返回此输出 [[-5，-1]，[1，3]，[4，12]，[15，20]]

repeating what I said before: I want it to return me this output [[-5, -1],[1, 3],[4, 12],[15, 20]]

我希望我的解释不会太夸张，因为我不是以英语为母语的人.谢谢！

I hope my explanation didn't turned out to be too prolix since I'm not a native english speaker. Thanks!

推荐答案

您可以使用functools中的reduce将间隔合并在一起:

You can use reduce from functools to merge the intervals together:

intervals = [[-5,-3],[-4,-1],[1,3],[4,8],[5,10],[10,12], [15,20]]

from functools import reduce
disjoints = [*reduce(lambda a,b: a+[b] if not a or b[0]>a[-1][1] else a[:-1]+[[a[-1][0],b[1]]],intervals,[])]

print(disjoints) # [[-5, -1], [1, 3], [4, 12], [15, 20]]

或在基本循环中做同样的事情:

or do the same thing in a basic loop:

disjoints = intervals[:1]
for s,e in intervals[1:]:
    if s>disjoints[-1][-1]: disjoints.append([s,e])
    else: disjoints[-1][-1] = e
    
print(disjoints) # [[-5, -1], [1, 3], [4, 12], [15, 20]]

注意:这假定包含范围.如果结尾是排他性的，请使用> = 而不是> .

note: this assumes inclusive ranges. If the end is exclusive use >= instead of >.

这篇关于我想输入间隔列表，并检查重叠间隔和非重叠间隔的并集间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！