小编use*_*258的帖子

我正在做在线课程并且遇到了这个问题.

第一行包含两个非负整数1≤n,m≤50000 - 一行中的段数和点数.接下来的n行包含两个整数a_i≤b_i,用于定义第i个段.下一行包含定义点的m个整数.所有整数的绝对值最多为10 ^ 8.对于每个段,从n-points表输出它使用的点数.

我的解决方案是:

for point in points:
    occurrence = 0
    for l, r in segments:
        if l <= point <= r:
           occurrence += 1
    print(occurrence),

该算法的复杂性为O(m*n),显然效率不高.解决这个问题的最佳方法是什么？任何帮助将不胜感激!

样本输入:

2 3
0 5
7 10
1 6 11

样本输出:

1 0 0

样本输入2:

1 3
-10 10
-100 100 0

样本输出2:

0 0 1