带区间算术序列的最大重叠

Question

我有n个有间隔的算术序列。我需要找到第一个点，其中大部分时间间隔重叠。序列是无限的。让我举一个有限序列的例子，其中我一共有8个序列。给予，

N=8。所以，有8个序列。这些序列如下：

1：{1，2，3，4，5，6，7，8}{17，18，19，20，21，22，23，24}

seq-2：{9,10,11,12，13,14,15,16}..{25,26,27,28，29,30,31,32}

seq-3：{1,2,3,4}..{9,10,11,12}..{17,18,19,20}..{25,26,27,28}

seq-4：{5,6,7,8}..{13,14,15,16}..{21,22,23,24}..{29,30,31,32}

seq-5：{5}..{13}..{21}..{29}

seq-6：{4}.{8}.{12}.{16}.{20}.{24}.{28}.{32}

seq-7：{9,11，13,15}..{25,27，29,31}

seq-8：{2}.{18}

在这里，第13点和第29点有最大的重叠与4圈以上。第一点是13。

可以用O( n)，O(n^2)，O(n^3)，O(n^4)，O(n log N)等有效算法求解。

Answer 1

我建议使用分配计数算法。

下面是具有3个样本序列的算法的简单演示：

seq-1: [{1,2,}..{9,10}]

seq-2: [{1,2,3}..{5,7,8}]

seq-3: [{2,3,4}..{6,7}..{9,10}]

您需要在所有序列中找到最大值。在这种情况下是10。

创建一个从0到10开始的由11个元素组成的int数组。

i   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
--------------------------------------------------
A[i]| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |  0 |

现在，我们通过将元素的值增加1来计算元素在所有序列中的出现。

seq-1：{1,2，}.{9，10}

This sequence contains 1, 2, 9, and 10.
Increase value at index 1, 2, 9, and 10 by 1.

i   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
--------------------------------------------------
A[i]| 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |  1 |

2：{1，2，3}.{5，7，8}

This sequence contains 1, 2, 3, 5, 7,and 8.
Increase value at index 1, 2, 3, 5, 7, and 8 by 1.

i   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
--------------------------------------------------
A[i]| 0 | 2 | 2 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |  1 |

seq-3：{2，3，4}.{6，7}.{9，10}

This sequence contains 2, 3, 4, 6, 7, 9, and 10.
Increase value at index 2, 3, 4, 6, 7, 9, and 10 by 1.

i   | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
--------------------------------------------------
A[i]| 0 | 2 | 3 | 2 | 1 | 1 | 1 | 2 | 1 | 2 |  2 |

最后，数字2在所有序列之间的最大重叠次数为3。

希望我的建议会有帮助！