algorithm - 点和段

Question

我正在上在线类(class)，但遇到了这个问题。

第一行包含两个非负整数 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

Answer 1

您可以使用 sweep line algorithm来解决这个问题。

首先，将每个线段分成两个点，打开点和关闭点。

将所有这些点与那些 m 个点相加，并根据它们的位置对它们进行排序。

遍历点列表，维护一个counter，每遇到一个open point，就增加counter，如果遇到end point，就减少.如果遇到列表m点中的一个点，则该点的结果就是此时counter的值。

For example 2, we have:

1 3
-10 10
-100 100 0

After sorting, what we have is:

-100 -10 0 10 100

At point -100, we have `counter = 0`

At point -10, this is open point, we increase `counter = 1`

At point 0, so result is 1

At point 10, this is close point, we decrease `counter = 0`

At point 100, result is 0

So, result for point -100 is 0, point 100 is 0 and point 0 is 1 as expected.

时间复杂度是O((n + m) log (n + m))。