Sam*_*urn 5 algorithm integer range counting
我已经被这个算法难住了一段时间。
假设有四个整数范围。每个范围都有一个开始值和一个结束值。
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))
那有意义吗？接近算法的好方法是什么？
您可以在 O(N ln N) 时间内（用于排序）解决此问题，然后用相同的时间输出结果。如果数字范围很大，则 O(N ln N) 优于注释中建议的方法的 O(M\xc2\xb7N) 时间（其中 M = 范围涵盖的数字的总范围）。
\n\n将 N 个范围按升序排序，以 Start 值作为键，例如在数组 S 中。初始化一个空优先级队列 P。将深度计数 D 初始化为零，并将当前 \xe2\x80\x9creach\xe2\x80\x9d 初始化为R = S[0].开始。
\n\n当 S[i].Start=R 时，将 S[i].End 推到 P 上并推进 i 和 D。当 S[i].Start>R 时，产生元组 (R, p.top, D)。将 P 弹出到 R，然后将 D 减 1，然后在 P.top==R 时弹出 P。
\n\n重复上面的段落，同时i<N。