当超过2对时，解决合并和排序对问题

Question

我有一个需要订购的成对对象的列表，必须合并相邻的成对对象。输入列表中对的原始顺序是随机的，没有重要性。在每一对中，我们可以确定第一个值永远不会大于第二个值。 看看这个例子中的整数

lst = [[1, 4], [17, 20], [2, 3], [16, 18], [6, 6], [6, 7], [9, 13], [21, 24]]

如果出现以下情况，两对应合并：

• 它们是重叠的，例如[16,18]和[17,20]->；[16,20]
• 他们是近邻，例如[17,20]和[21,24]->；[17,24]
• 具体来说[6,6]和[6,7]也应该合并，成为[6,7]

然后对所有对进行排序（这很容易），因此查看示例数据，最终结果为：

ref = [[1, 4], [6, 7], [9, 13], [16, 24]]

我有一个函数mrg2pairs（pair_a，pair_b），它将返回一个或两个pair的列表。如果合并合适，则返回一个合并对，否则返回列表中的原始两对。 这就解决了2对的情况，我希望找到一种平滑的方法来处理较长的列表。 也许是递归的，使用mrg2pairs（），但我无法想象解决方案

def mrg2pairs(pair_a, pair_b):
    """ Merge two pairs
    :param pair_a: First pair
    :param pair_b: Second pair
    :return: A list of, one or two, pairs, each same format as pair_a and pair_b
    """
    a1, a2 = pair_a[0], pair_a[1]
    b1, b2 = pair_b[0], pair_b[1]
    if a1 < b1:
        if (b1 - a2) > 1:  # a entirely before b
            return [pair_a, pair_b]  # return untouched
        elif a2 == b1:  # a-end touching b-start
            return [[a1, b2]]  # merge
        else:
            if a2 < b2: # a overlapping b-start
                return [[a1, b2]]
            else:  # a encapsulating b
                return [pair_a]  # return a
    else:
        if a1 < b2:
            if a2 > b2:  # a overlapping b-end
                return [[b1, a2]]
            else:  # a inside b
                return [pair_b]  # return b
        else:
            if (a1 - b2) > 1:  # a entirely after b
                return [pair_a, pair_b]  # return untouched
            else:  # a-start touching b-end
                return [[b1, a2]]  # merge

该函数经过测试，工作正常-问题是如何在列表情况下从2线对情况转到n线对情况

我需要用Python解决这个问题-欢迎任何建议，但我更喜欢Python优雅

Answer 1

下面的解决方案是可行的，但我觉得它并不像我希望的那样优雅

def mrg_many(lst_pairs):
    """ Merge many pairs
    :param lst_pairs: List of pairs
    :return: A list of pairs, where all appropriate merges is made
    """
    lst_ret = [itm for itm in lst_pairs]  # deep copy
    lst_rem = list()
    for n in range(len(lst_pairs)):
        for m in range(n+1, len(lst_pairs)):
            mp_ret = mrg2pairs(lst_pairs[n], lst_pairs[m])
            if len(mp_ret) == 1:
                if mp_ret[0] not in lst_ret:
                    lst_ret.append(mp_ret[0])
                lst_rem.extend([itm for itm in [lst_pairs[n], lst_pairs[m]] if itm not in mp_ret])
    lst_resul = [itm for itm in lst_ret if itm not in lst_rem]
    if any([itm not in lst_resul for itm in lst_pairs]):  # at least one pair from input disappeared
        return mrg_many(lst_resul)
    return lst_resul

Answer 2

您可以使用对分模块获得O（NlogN）解决方案，而无需实际排序：

lst = [[1, 4], [17, 20], [2, 3], [16, 18], [6, 6], [6, 7], [9, 13], [21, 24]]

from bisect import bisect_left
starts = []  # merged starting values
ends   = []  # merged ending values
for (start,end) in lst:
    iLeft  = bisect_left(ends,start-1) # first position after start
    iRight = bisect_left(starts,end+1) # first position after end
    starts[iLeft:iRight] = [min([start]+starts[iLeft:iLeft+1])] # insert/merge
    ends[iLeft:iRight]   = [max([end]+ends[iRight-1:iRight])]        
merged = list(zip(starts,ends)) # combine starts and ends

print(merged)
[(1, 4), (6, 7), (9, 13), (16, 24)]