algorithm - 计算整数范围的重叠

Question

我被这个算法难住了很长时间。

假设有四个整数范围。每个范围都有一个开始值和一个结束值。

Range A: 0,5
Range B: 4,12
Range C: 2,10
Range D: 8,14

根据这些值，我想得到一个新集合，它计算落在特定整数范围内的范围数。其中每一个都有 Start、End 和 Count 值，产生如下内容:

(Start, End, Count)
0,1,1   (Only 1 range (A) falls between 0 and 1 inclusive)
2,3,2   (2 ranges (A,C))
4,5,3   (3 ranges (A,B,C))
6,7,2   (2 ranges (B,C))
8,10,3  (3 ranges (B,C,D))
11,12,2 (2 ranges (B,D))
13,14,1 (1 range (D))

这有意义吗？处理该算法的好方法是什么？

Answer 1

您可以在 O(N ln N) 时间内(排序)解决此问题，然后用相同的时间输出结果。如果数字范围很大，O(N ln N) 优于评论中建议的方法的 O(M·N) 时间(其中 M = 范围涵盖的数字的总范围)。

将 N 个范围按升序排序，以起始值为键，例如在数组 S 中。初始化一个空的优先级队列 P。将深度计数 D 初始化为零，当前“到达”到 R = S[0] .开始。

当 S[i].Start=R 时，将 S[i].End 推到 P 上并推进 i 和 D。当 S[i].Start>R 时，产生元组 (R, p.top, D) .将 P 弹出到 R，然后将 D 减一并在 P.top==R 时弹出 P。

同时i<N重复以上段落.