Максимальное перекрытие арифметических c последовательностей с интервалами

Question

у меня есть число арифметических c последовательностей с интервалами. Мне нужно найти первую точку, в которой большинство этих интервалов перекрываются. Последовательности бесконечны. Позвольте мне привести пример для конечных последовательностей, где у меня всего 8 последовательностей. Учитывая,

N = 8. Итак, есть 8 последовательностей. Последовательности следующие:

seq-1: [{1,2,3,4,5,6,7,8} .. {17,18,19,20,21,22,23 , 24}]

сек-2: [{9,10,11,12, 13 , 14,15,16} .. {25,26,27,28, 29 , 30,31,32}]

сек-3: [{1,2,3,4} .. {9,10,11,12} .. {17, 18,19,20} .. {25,26,27,28}]

сек-4: [{5,6,7,8} .. { 13 , 14 , 15,16} .. {21,22,23,24} .. { 29 , 30,31,32}]

seq-5: [{5} .. { 13 } .. {21} .. { 29 }]

сек-6: [{4} .. {8} .. {12} .. {16} .. {20} .. {24} .. {28} .. {32}]

сек-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) et c. Здесь значение n равно 8.

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.

Создайте массив int из 11 элементов, начиная с 0 до 10.

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 |

seq-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 |

сек-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 между всеми последовательностями.

Надеюсь, мое предложение поможет!