如何为bisect.bisect_left编写满足双元素均≤规则的键函数？

首先要明确：Python的bisect模块依赖全序关系（任意两个元素都能确定先后顺序），但你要求的是偏序关系（仅当[x1,y1]的两个元素都≤[x2,y2]时，前者排在后者前，否则可能无法比较），因此无法直接给bisect_left传入键函数来实现需求。我们需要换一种思路来统计能容纳点(x,y)的矩形数量。

可行解决方案 #

核心思路是通过两步二分查找，先筛选出x坐标符合条件的矩形，再在其中统计y坐标符合条件的数量：

• 预处理排序：将矩形列表按x升序排序，若x相同则按y升序排序。这样能保证所有x≤目标x的矩形都集中在列表的前半部分。
• 第一步二分：用bisect_right找到第一个x大于目标x的矩形索引，该索引之前的所有矩形都满足x≤目标x。
• 第二步二分：在第一步筛选出的矩形的y值列表中，再次用bisect_right统计y≤目标y的数量，这个数量就是能容纳点(x,y)的矩形总数。

代码示例 #

import bisect

# 示例矩形列表
rectangles = [[1, 2], [3, 4], [2, 3], [1, 3], [2, 1]]
# 按x升序、x相同则y升序排序
rectangles.sort(key=lambda r: (r[0], r[1]))

# 提取排序后的x和y列表，方便后续二分
xs = [r[0] for r in rectangles]
ys = [r[1] for r in rectangles]

# 目标点(x,y)
target_x, target_y = 2, 3

# 第一步：找到所有x <= target_x的矩形的右边界
x_bound = bisect.bisect_right(xs, target_x)
# 第二步：在这些矩形中统计y <= target_y的数量
valid_count = bisect.bisect_right(ys[:x_bound], target_y)

print(f"能容纳点({target_x},{target_y})的矩形数量：{valid_count}")
# 输出：能容纳点(2,3)的矩形数量：4
# 符合条件的矩形是[1,2], [1,3], [2,1], [2,3]

关键说明 #

• 如果目标点没有符合条件的矩形（比如点(0,0)），valid_count会返回0，完全匹配你的需求。
• 这种方法的时间复杂度是O(n log n)（排序） + O(log n)（两次二分），效率远高于遍历整个列表统计。

内容的提问来源于stack exchange，提问作者Aviral Srivastava