algorithm - 如何获得重叠集中的碰撞次数？

Question

对于我正在做的一个项目，我有一个

形式的集合列表

[[开始，结束]]

例如

[{1, 3} {2, 4} {5, 9} {6, 8} {7, 8}]

数组是有序的。

我想找出重叠碰撞的次数。例如来自示例数据集。

我想要的结果是这样的

 Interval | Collisions
----------------------
 {7,8}    | 3
 {2,3}    | 2
 {6,7}    | 2
 {1,2}    | 1
 {3,4}    | 1
 {5,6}    | 1
 {8,9}    | 1

实现它的理想方法是什么？

Answer 1

您可以将每个列表元素转换为两个 元素，一个代表开始，一个代表结束。然后，对结果进行排序，给你这个:

• 从 1 开始
• 2 点开始
• 3 点结束
• 4 点结束
• 5 点开始
• 6 点开始
• 7 点开始
• 8 点结束
• 8 点结束
• 9 点结束

现在您可以遍历列表，跟踪您在每个点进入和退出的集合数。