输入参数是代表间隔的元组列表和整数列表。目标是编写一个函数来计算每个整数所在的间隔数，并将结果作为关联数组返回。例如：
Input intervals: [(1, 3), (5, 6), (6, 9)] Input integers: [2, 4, 6, 8] Output: {2: 1, 4: 0, 6: 2, 8: 1}
其他例子：
Input intervals: [(3, 3), (22, 30), (17, 29), (7, 12), (12, 34), (18, 38), (30, 40), (5, 27), (19, 26), (27, 27), (1, 31), (17, 17), (22, 25), (6, 14), (5, 7), (9, 19), (24, 28), (19, 40), (9, 36), (2, 32)] Input numbers: [16, 18, 39, 40, 27, 28, 4, 23, 15, 24, 2, 6, 32, 17, 21, 29, 31, 7, 20, 10] Output: {2: 2, 4: 2, 6: 5, 7: 6, 10: 7, 15: 6, 16: 6, 17: 8, 18: 8, 20: 9, 21: 9, 23: 11, 24: 12, 27: 11, 28: 9, 29: 8, 31: 7, 32: 6, 39: 2, 40: 2}
我该如何编写一个可以有效执行此操作的函数？我已经有了 O(nm) 实现，其中 n 是间隔数，m 是整数数，但我正在寻找更有效的方法。
我目前拥有的：
def intervals_per_number(numbers, intervals): result_map = {i: 0 for i in numbers} for i in result_map.keys(): for k in intervals: if k[0] <= i <= k[1]: result_map[i] += 1 return result_map
希望我解释得足够清楚。如果还有什么不清楚的地方请告诉我。
将整数、起点和终点放在一个成对的列表中。将每对的第一个元素设为整数、起点或终点的值，将每对的第二个元素设为 0、-1 或 1，具体取决于它是整数、起点还是终点。
接下来，对列表进行排序。
现在，您可以浏览列表，维护对的第二个元素的运行总和。当您看到第二个元素为 0 的对时，记录该整数的运行总和（取反）。
在最坏的情况下，这会在 O((N+M)log(N+M)) 时间内运行（实际上，我猜如果查询和间隔大多已排序，它将是线性的，这要归功于 timsort）。
例如：
Input intervals: [(1, 3), (5, 6), (6, 9)] Input integers: [2, 4, 6, 8] Unified list (sorted): [(1,-1), (2,0), (3,1), (4,0), (5,-1), (6, -1), (6,0), (6,1), (8,0), (9,1)] Running sum: [-1 , -1, 0, 0, -1, -2, 0, -1, -1, 0] Values for integers: 2: 1, 4: 0, 6: 2, 8, 1
示例代码：
def query(qs, intervals): xs = [(q, 0) for q in qs] + [(x, -1) for x, _ in intervals] + [(x, 1) for _, x in intervals] S, r = 0, dict() for v, s in sorted(xs): if s == 0: r[v] = S S -= s return r intervals = [(3, 3), (22, 30), (17, 29), (7, 12), (12, 34), (18, 38), (30, 40), (5, 27), (19, 26), (27, 27), (1, 31), (17, 17), (22, 25), (6, 14), (5, 7), (9, 19), (24, 28), (19, 40), (9, 36), (2, 32)] queries = [16, 18, 39, 40, 27, 28, 4, 23, 15, 24, 2, 6, 32, 17, 21, 29, 31, 7, 20, 10] print(query(queries, intervals))
输出：
{2: 2, 4: 2, 6: 5, 7: 6, 10: 7, 15: 6, 16: 6, 17: 8, 18: 8, 20: 9, 21: 9, 23: 11, 24: 12, 27: 11, 28: 9, 29: 8, 31: 7, 32: 6, 39: 2, 40: 2}
