Подсчет перекрытий целочисленных диапазонов

Я довольно долго был в тупике по поводу этого алгоритма.

Скажем, есть четыре диапазона целых чисел. У каждого диапазона есть начальное и конечное значение.

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

Имеет ли это смысл? Как лучше подойти к алгоритму?


range algorithm counting integer
person Sam Washburn    schedule 16.06.2013    source источник
comment
Какой алгоритм вам нужен, будет зависеть от вашего варианта использования - каково максимальное количество диапазонов, с которыми вы ожидаете иметь дело, и максимальный размер диапазона?   -  person Patashu    schedule 17.06.2013
comment
@Patashu Максимальное количество диапазонов должно быть от сотен до нескольких тысяч, как и размер диапазона.   -  person Sam Washburn    schedule 17.06.2013
comment
Если вам не нужно запоминать, какие диапазоны охватывают какие числа, а только количество диапазонов, которые его охватывают, создайте массив с индексами 0 ... n, где n - наибольший максимум любого диапазона, и для каждого диапазона увеличивайте все элементы покрываемого им массива на 1.   -  person Patashu    schedule 17.06.2013
comment
Вот и все - jsfiddle.net/vsync/jrbb471h   -  person vsync    schedule 30.03.2016
comment
@vsync Довольно круто. Хотя это было почти 3 года назад. Я даже не помню, что кодировал. Ржу не могу.   -  person Sam Washburn    schedule 30.03.2016
comment
Выложу как ответ. Я тоже сейчас размышляю над этой проблемой   -  person vsync    schedule 30.03.2016

Ответы (3)


arrow_upward
3
arrow_downward

Вы можете решить эту проблему за O (N ln N) времени (для сортировки), за которым следует такое же количество времени для вывода результатов. Если диапазон чисел большой, O (N ln N) лучше, чем время O (M · N) метода, предложенного в комментарии (где M = общий диапазон чисел, охватываемых диапазонами).

Отсортируйте N диапазонов в порядке возрастания, используя начальное значение, например, в массиве S. Инициализируйте пустую приоритетную очередь P. Инициализируйте счетчик глубины D равным нулю, а текущий «охват» равным R = S [0] .Start.

Пока S [i] .Start = R, нажмите S [i] .End на P и продвиньте i и D. Когда S [i] .Start> R, получите кортеж (R, p.top, D). Вставьте P в R, затем уменьшите D на единицу и нажмите P, пока P.top == R.

Повторите предыдущий абзац, пока i<N.

person James Waldby - jwpat7    schedule 17.06.2013
comment
Для более подробного объяснения см. Также Дерево интервалов - person Frank Sebastià; 13.07.2017

arrow_upward
1
arrow_downward 

function checkOverlap(arr){
  var overlaps = {}, i, j;
  // match each item against all others BUT itself
  for( i=0; i < arr.length; i++ )
      for( j=0; j < arr.length; j++ )
          if( arr[i] !== arr[j] && arr[i][1] < arr[j][2] && arr[j][1] < arr[i][2] )
            overlaps[arr[i][0]] = 1;

  return Object.keys(overlaps);
}

Запустите его с массивом диапазонов, например:

[
  ["a", 10, 12], 
  ["b", 20, 30], 
  ["c", 29, 30], 
  ["d", 15, 95], 
  ["e", 195, 196]
];

Демоверсия Playgroud

person vsync    schedule 30.03.2016

arrow_upward
0
arrow_downward

Диапазон x пересекает входной диапазон y, если:

x.End >= y.Start AND y.End >= x.Start

Итак, для заданного ввода просто прокрутите свою коллекцию диапазонов и посмотрите, какие из них удовлетворяют вышеуказанному условию.

Если данная коллекция диапазонов не меняется очень часто, и ваша коллекция диапазонов становится намного больше, чем 4, которые вы указали в описании проблемы, то сначала отсортируйте их, чтобы вы могли более эффективно искать диапазоны, которые пересекают ваш ввод, вместо того, чтобы перебирать их все.

Если данная коллекция диапазонов часто меняется, сортировка может оказаться слишком дорогой, и тогда будет разумнее просто перебирать их все в цикле каждый раз.

person mbeckish    schedule 17.06.2013