Python实现查找含最多交集的区间功能,现有代码不满足需求求助
代码问题说明
你当前实现的是区间合并功能,逻辑是将所有重叠/相邻的区间合并为连续的大区间,和「找到交集数量最多的区间」的需求完全不匹配。
实现思路
- 先统计每个区间与其他区间的相交次数,闭区间相交的判断条件为:
区间A的左端点 <= 区间B的右端点 且 区间B的左端点 <= 区间A的右端点 - 筛选出相交次数最大的区间集合:如果最大相交次数为0,说明所有区间无交集,直接返回
-1 - 从相交次数最大的区间中,选择长度最短的区间作为结果(长度计算为
右端点 - 左端点,和闭区间元素数的大小比较结果一致)
完整实现代码
def find_max_intersection_interval(intervals): n = len(intervals) if n == 0: return -1 if n == 1: return intervals[0] # 统计每个区间的相交次数 intersect_counts = [] for i in range(n): cnt = 0 a_start, a_end = intervals[i] for j in range(n): if i == j: continue b_start, b_end = intervals[j] # 判断闭区间是否相交 if a_start <= b_end and b_start <= a_end: cnt += 1 intersect_counts.append(cnt) max_cnt = max(intersect_counts) # 所有区间无交集 if max_cnt == 0: return -1 # 筛选出相交次数最大的区间 candidate_intervals = [intervals[i] for i in range(n) if intersect_counts[i] == max_cnt] # 选长度最短的区间 candidate_intervals.sort(key=lambda x: (x[1] - x[0])) return candidate_intervals[0]
测试用例验证
- 测试用例1:输入
[[1,5],[5,10],[5,5]],返回[5,5],符合规则 - 测试用例2:输入
[[1,2],[3,5]],返回-1,符合规则 - 测试用例3:输入
[(1,6), (2,3), (4,11)],返回(1,6),符合预期
内容的提问来源于stack exchange,提问作者pikas
相关产品推荐
相关产品推荐

