Тестирование перекрывающихся массивов в Ruby

Question

Скажем, у меня есть массив массивов в Ruby,

[[100,300], 
 [400,500]]

что я строю, добавляя последовательные строки данных CSV.

Как лучше всего при добавлении нового подмассива проверить, покрывается ли диапазон, охватываемый двумя числами в подмассиве, любыми предыдущими подмассивами?

Другими словами, каждый подмассив содержит линейный диапазон (100-300 и 400-500) в приведенном выше примере. Если я хочу, чтобы было выдано исключение, если я попытался добавить [499 501], например, в массив, потому что там будет перекрытие, как я могу лучше всего проверить это?

Answer 1

Так как ваши подмассивы должны представлять диапазоны, было бы неплохо использовать массив диапазонов вместо массива.

Таким образом, ваш массив становится [100..300, 400..500],

Для двух диапазонов мы можем легко определить метод, который проверяет, перекрываются ли два диапазона:

def overlap?(r1, r2)
  r1.include?(r2.begin) || r2.include?(r1.begin)
end

Теперь, чтобы проверить, есть ли диапазон r перекрывается с любым диапазоном в вашем массиве диапазонов, вам просто нужно проверить, overlap?(r, r2) верно для любого r2 в массиве диапазонов:

def any_overlap?(r, ranges)
  ranges.any? do |r2|
    overlap?(r, r2)
  end
end

Который можно использовать так:

any_overlap?(499..501, [100..300, 400..500])
#=> true

any_overlap?(599..601, [100..300, 400..500])
#=> false

Вот any_overlap? принимает O(n) время. Так что если вы используете any_overlap? каждый раз, когда вы добавляете диапазон в массив, все будет O(n**2),

Однако есть способ сделать то, что вы хотите, не проверяя каждый диапазон:

Вы добавляете все диапазоны в массив без проверки на перекрытие. Затем вы проверяете, перекрывает ли какой-либо диапазон в массиве какой-либо другой. Вы можете сделать это эффективно в O(n log n) время, сортируя массив в начале каждого диапазона, а затем проверяя, перекрываются ли два соседних диапазона:

def any_overlap?(ranges)
  ranges.sort_by(&:begin).each_cons(2).any? do |r1,r2|
    overlap?(r1, r2)
  end
end

Answer 2

Используйте multi_range и звоните overlaps? метод проверки, есть ли перекрытия:

MultiRange.new([100..300, 400..500]).overlaps?(499..501)

Обратите внимание, что вам может потребоваться преобразовать введенные вами данные из массива массивов в массив диапазонов перед его использованием. Возможный рабочий пример:

arrays = [[100, 300], [400, 500]]
subarray = [499, 501]

ranges = arrays.map{|a, b| a..b }
MultiRange.new(ranges).overlaps?(subarray[0].. subarray[1])
# => true