计算整数范围的重叠 [英] Counting Overlaps of Integer Ranges

问题描述

我已经被这个算法困住了很多。

I've been stumped on this algorithm for quite a bit.

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

Say there are four ranges of integers. Each range has a Start and an End value.

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

来自这些值我希望得到一个新的集合，它计算特定跨度内的范围数量。每个都有开始，结束和计数值，产生如下：

From these values I would like to get a new set which counts of the number of the ranges that fall in a particular span of ints. Each of these would have Start, End and Count values, producing something like this:

(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))

这有意义吗？什么是接近算法的好方法？

Does that make sense? What's a good way to approach the algorithm?

推荐答案

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

You can solve this in O(N ln N) time (for sorting) followed by the same amount of time for outputting results. If the number range is large, O(N ln N) is better than the O(M·N) time of the method suggested in a comment (where M = total range of numbers covered by the ranges).

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

Sort the N ranges into ascending order, keyed by Start value, say in array S. Initialize an empty priority queue P. Initialize a depth-count D to zero, and the current "reach" to R = S[0].Start.

当S [i] .Start = R时，按下S [i]。结束P并前进i和D.当S [i] .Start> R时，产生元组（R，p.top，D）。弹出P到R然后将D减少一个并弹出P而P.top == R.

While S[i].Start=R, push S[i].End on P and advance i and D. When S[i].Start>R, yield the tuple (R, p.top, D). Pop P to R and then decrease D by one and pop P while P.top==R.

在 i< N 时重复上述段落。

这篇关于计算整数范围的重叠的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！