查找多个客户端之间的所有公共范围

Question

我对编码比较陌生。我遇到了一个无法解决的问题。

我有多个"客户"。，每个客户端都有几个有效的范围(用开始和结束点标记-例如(5,10)，其中5是开始点，10是结束点)。我需要找到一个代码，找到所有客户端的公共范围(如果这样的范围不存在，然后找到除1以外的所有客户端的公共范围，依此类推…)

我考虑过简单地计算所有可能的排列，但是我不能让它工作(除了计算效率低下)。

重要提示-客户端数量和每个客户端的范围不是预先确定的，但可以在运行时计算。

简单的例子-假设我有7个客户机，如下所示:

1. 客户端1 -范围为(17,30)，(34,44)
2. 客户端2 -范围为(17,30)，(31,44)
3. 客户端3 -范围为(25,30)，(34,44)
4. 客户端4 -范围为(18,30)，(34,44)
5. 客户端5 -范围为(19,44)
6. 客户端6 -范围为(20,37)，(38,44)
7. 客户端7 -范围为(20,37)

代码应该输出(给定此配置)以下范围-(25,30)和(34,37)

我希望我正确地描述了这个问题，如果有必要，我很乐意澄清。

提前感谢!!

Answer 1

这个方法创建一个"数轴";对于开始和停止单个范围的点，然后从最小点向上遍历数轴，每开始一个范围计算占用+1，每停止一个范围计算占用-1。

的代码

"""
See: https://stackoverflow.com/questions/65812746/finding-all-common-ranges-finding-between-multiple-clients
Created on Wed Jan 20 17:28:44 2021
@author: Paddy3118
"""
from collections import defaultdict

clients = [[(17,30), (34,44)],
[(17,30), (31,44)],
[(25,30), (34,44)],
[(18,30), (34,44)],
[(19,44)],
[(20, 37), (38,44)],
[(20, 37)],
]
def ranges_singly(clients):
"give each (lo, hi) range individually"
return ([lo, hi] for c_ranges in clients for lo, hi in c_ranges)
def combine_ranges(c=clients):
LO, HI = 'LO', 'HI'
endpt = defaultdict(list)
for lo, hi in ranges_singly(c):
endpt[lo].append(LO)
endpt[hi].append(HI)
pt_order = sorted(endpt)
last_pt, n  = None, 0
sub_ranges = []
for pt in pt_order:
if n == 0:  # No clients in last_pt..pt
pass
else:
sub_ranges.append((last_pt, pt, n))
n += endpt[pt].count(LO)    # Ranges starting here
n -= endpt[pt].count(HI)    # Ranges ending here
last_pt = pt
assert n == 0, f'Whoops n should end at zero not {n}'
max_n = max(sub_ranges, key=lambda r:r[2])[-1]
return max_n, [(lo, hi) for lo, hi, n in sub_ranges if n == max_n]
if __name__ ==  '__main__':
print(combine_ranges(clients))      # (7, [(25, 30), (34, 37)])