给定整数区间列表与整数列表，如何高效按区间分组整数

首先可以确定，在区间无重叠（你给出的示例也满足该条件）的场景下，存在远优于嵌套循环O(N*M)复杂度的实现，数值范围有限时可做到严格O(N)，通用场景下复杂度为O(M log M + N log M)（M为区间数量，N为整数列表B的长度），具体实现如下：

方案1：数值范围有限场景的严格O(N)实现 #

• 适用条件：所有区间的端点最大值不超过可接受的内存开销范围（比如最大值<=1e6）
• 实现步骤：
  1. 初始化字典或数组pos_map，用于存储每个整数对应的所属区间
  2. 遍历所有区间，将区间内每一个整数对应的pos_map[x]设为当前区间的标识（如首尾组成的元组），时间复杂度为O(所有区间总长度)，总长度与N同量级时整体复杂度为O(N)
  3. 遍历B中的每个元素，直接查pos_map获取对应区间，将元素加入对应结果集合即可，单次查询O(1)，总复杂度O(N)

方案2：任意无重叠区间的通用高效实现 #

• 适用条件：无区间跨度限制，是绝大部分场景下的最优选择
• 实现步骤：
  1. 先将区间列表A按左端点从小到大排序，因为区间无重叠，排序后右端点也会严格递增，复杂度O(M log M)
  2. 提取所有排序后区间的左端点，组成单独的数组left_points
  3. 遍历B中的每个元素x，用二分查找在left_points中找到最后一个小于等于x的索引，该索引对应的区间就是x的候选归属区间，再判断x是否小于等于该区间的右端点即可完成归属判断，单次查找复杂度O(log M)，总复杂度O(N log M)

你的示例中排序后区间为[[1,5],[6,9],[13,18]]，左端点数组为[1,6,13]，查找x=7时二分得到最后一个小于等于7的左端点为6，对应区间[6,9]，判断7<=9即确认归属，完全符合预期

附Python实现代码：

import bisect
from collections import defaultdict

def group_by_interval(intervals, nums):
    # 按左端点排序区间
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    left_points = [itv[0] for itv in sorted_intervals]
    result = defaultdict(list)
    for num in nums:
        # 二分查找定位候选区间
        idx = bisect.bisect_right(left_points, num) - 1
        # 验证是否在区间范围内
        if idx >= 0 and num <= sorted_intervals[idx][1]:
            result[tuple(sorted_intervals[idx])].append(num)
    return result

# 测试用例
A = [[1,5], [13, 18], [6,9]]
B = [3, 15, 16, 7, 8, 9]
print(group_by_interval(A, B))
# 输出：{(1, 5): [3], (6, 9): [7, 8, 9], (13, 18): [15, 16]}

如果区间允许重叠的话，可以在找到候选索引后，向后遍历所有左端点<=x的区间，判断x是否<=右端点即可，平均性能仍远优于嵌套循环。

内容的提问来源于stack exchange，提问作者Ninja Dude