ОП определил 2-элементные массивы "не разрешено", [i,j], j >= i. Я считаю более информативным ссылаться на диапазоны "не подлежать покрытию" ( NTBC ), i..j, j >= i. Учитывая положительное целое число n и массив arr диапазонов NTBC, цель состоит в том, чтобы определить число диапазонов, охватываемых 1..n, которые охватывают none диапазонов NTBC;то есть подсчитайте те диапазоны i..j, для которых:
arr.any? { |r| (i..j).cover? r } == false
Здесь и далее, когда я ссылаюсь на диапазон i..j, следует предполагать, что i и j удовлетворяютусловие 1 <= i <= j <= n.
Я ссылаюсь на два диапазона NTBC i..j и p..q как с перекрытием , если i < p < q < j или p < i < q < j. Ниже я приведу очень быстрое решение для случая, когда нет перекрывающихся диапазонов NTBC. ОП заявил, что диапазоны NTBC могут перекрываться, поэтому мое решение не дает полного ответа. Проблема состоит в том, что наличие перекрывающихся диапазонов разрушает математическую структуру, требуемую комбинаторным алгоритмом, который я использую. Тем не менее я решил представить свое решение в надежде, что кто-то найдет способ расширить мои идеи до случая, когда диапазоны NTBC могут перекрываться.
Создать count_ranges метод
Давайте сначала создадим метод, который с учетом целых чисел i и j, i <= j подсчитывает количество диапазонов p..q, таких, что i <= p <= q <= j;то есть для чего (i..j).cover?(p,q) #=> true. Например,
(20..40).cover?(12..18) #=> false
(20..40).cover?(14..28) #=> false
(20..40).cover?(23..37) #=> true
(20..40).cover?(29..47) #=> false
(20..40).cover?(43..51) #=> false
См. Range # cover? для случая, когда аргумент является диапазоном. Метод следующий.
def count_ranges(i,j)
return 0 if j < i
n = (j-i+1)
n**2 - (n-1)*n/2
end
Например:
count_ranges(1,4) #=> 10
Это будут 10 диапазоны:
1..1, 1..2, 1..3, 1..4,
2..2, 2..3, 2..4,
3..3, 3..4,
4..4
Обратите внимание:
count_ranges(3,6) #=> 10
или, в более общем смысле,
count_ranges(n,n+3) #=> 10
Обоснование расчетов, выполненных этим методом, заключается в следующем. Учитывая диапазон i..j, i <= j, число диапазонов, охватываемых этим диапазоном, рассчитывается следующим образом.
n = j-i+1
n + n-1 + n-2 + ... + n-(n-1)
= n*n - (1 + 2 +...+ n-1)
= n*n - (n-1)*n/2
n равно количеству диапазонов, которые начинаются с i и заканчиваются наk, где i <= k <= j. n-1 равно количеству диапазонов, которые начинаются с i+1 и заканчиваются k, i+1 <= k <= j и т. Д. n-(n-1) #=> 1 равно числу диапазонов, которые начинаются с i+(n-1) #=> i+(j-i+1-1) => j и заканчиваются k, j <= k <= j.
(1 + 2 +...+ n-1) - это сумма арифметической последовательности, которая равна произведению числаэлементы в последовательности (n-1) и среднее значение в последовательности, равное сумме первого и последнего элементов (1+(n-1) #=> n), деленное на 2.
Этот метод выполняет всю работув коде ниже. Важно отметить, что скорость выполнения этого метода практически не зависит от величин двух его аргументов.
Удалить избыточные диапазоны NTBC
Пусть arr будетмассив диапазонов NTBC. Первым шагом является удаление диапазонов NTBC, которые охватывают другой диапазон NTBC. Если:
r1 = u..v
r2 = x..w
и u <= x =< w <= v (r1.cover?(r2) #=> true), r1 является избыточным и поэтому может игнорироваться, так как любой диапазон r, который исключается из подсчета, поскольку r.cover?(r1) #=> true будетдисквалифицируется r2, если r1 не было.
require 'set'
def remove_redundant_ranges(arr)
set = Set.new
a = arr.dup
while a.any?
r = a.shift
set << r unless set.any? { |t| r.cover?(t) } || a.any? { |t| r.cover?(t) }
end
set.to_a
end
Например:
arr = [2..4, 7..14, 8..12, 14..14, 4..5, 1..5, 9..12, 2..4]
remove_redundant_ranges(arr)
#=> [14..14, 4..5, 9..12, 2..4]
Метод подсчета
def count_non_covering_ranges(n, arr)
(([0..0] + remove_redundant_ranges(arr).sort_by(&:begin)) << (n+1..n+1)).
each_cons(2).
sum { |r1,r2| net_count(r1, r2) }
end
def net_count(r1, r2)
r1b, r1e = endpoints(r1)
r2b, r2e = endpoints(r2)
count_ranges(r1b+1, r2e-1) - count_ranges(r1b+1, r1e-1)
end
def endpoints(r)
[r.begin, r.end]
end
Примеры
Пример 1
n = 9
arr = [2..4, 4..5, 7..9]
count_non_covering_ranges(n, arr)
#=> 20
Диапазоны 20, охватываемые 1..9, которые не охватывают диапазоны NTBCв arr:
1..1, 1..2, 1..3,
2..2, 2..3,
3..3, 3..4,
4..4,
5..5, 5..6, 5..7, 5..8,
6..6, 6..7, 6..8,
7..7, 7..8,
8..8, 8..9
9..9
Пример 2
n = 12
arr = [2..4, 4..7, 9..11]
count_non_covering_ranges(n, arr)
#=> 38
38 диапазоны, охватываемые 1..12, которые не охватывают диапазоны NTBC в arr, следующие:
1..1, 1..2, 1..3,
2..2, 2..3,
3..3, 3..4, 3..5, 3..6,
4..4, 4..5, 4..6,
5..5, 5..6, 5..7, 5..8, 5..9, 5..10,
6..6, 6..7, 6..8, 6..9, 6..10,
7..7, 7..8, 7..9, 7..10,
8..8, 8..9, 8..10,
9..9, 9..10,
10..10, 10..11, 10..12,
11..11, 11..12,
12..12
Пример 3
n = 12
arr = [2..4, 6..8, 9..11]
count_non_covering_ranges(n, arr)
#=> 34
Диапазоны 34, охватываемые 1..12, которые не охватывают диапазоны NTBC в arr, следующие:
1..1, 1..2, 1..3,
2..2, 2..3,
3..3, 3..4, 3..5, 3..6, 3..7
4..4, 4..5, 4..6, 4..7
5..5, 5..6, 5..7,
6..6, 6..7,
7..7, 7..8, 7..9, 7..10,
8..8, 8..9, 8..10,
9..9, 9..10,
10..10, 10..11, 10..12,
11..11, 11..12,
12..12
Пример 4
n = 15
arr = [2..4, 4..5, 9..12, 14..14]
count_non_covering_ranges(n, arr)
#=> 44
Диапазоны 44, охватываемые 1..15, которые не охватывают диапазоны NTBC в arr следующие.
1..1, 1..2, 1..3,
2..2, 2..3,
3..3,
4..4,
5..5, 5..6, 5..7, 5..8, 5..9, 5..10, 5..11,
6..6, 6..7, 6..8, 6..9, 6..10, 6..11,
7..7, 7..8, 7..9, 7..10, 7..11,
8..8, 8..9, 8..10, 8..11,
9..9, 9..10, 9..11,
10..10, 10..11,
11..11,
10..12, 10..13,
11..12, 11..13,
12..12, 12..13,
13..13,
15..15
Пример 5
n = 15
arr = [2..4, 4..5, 9..12, 14..14]
require 'time'
n = 1_000_000_000_000
m = 1_000 # number of NTBC ranges
s = 1_000 # size of each NTBC range
q = n/m
arr = m.times.map do |i|
from = rand(i*q..(i+1)*q-1-s)
from..from+s-1
end
arr.first(3)
#=> [737321450..737322449, 1803846784..1803847783, 2536962375..2536963374]
arr.last(2)
#=> [998900666529..998900667528, 999036273747..999036274746]
t = Time.now
x = count_non_covering_ranges(n, arr)
#=> 585_410_016_606_600_423_738
puts "#{(Time.now-t).round(2)} seconds"
0.24 seconds
Объяснение
См. Enumerable # each_cons .
Первое, на что нужно обратить внимание, это то, что скорость выполнения count_non_covering_ranges практически не зависитвеличины его первого аргумента, n, и размеров диапазонов NTBC, и приблизительно пропорционально размеру его второго аргумента, arr, числу диапазонов NTBC.
Предположим:
n = 14
arr = [2..5, 7..9, 10..13]
Сначала мы изменим это следующим образом:
r1 = 0..0
r2 = 2..5
r3 = 7..9
r4 = 10..13
r5 = n+1..n+1 #=> 15..15
a = [r1, r2, r3, r4, r5]
Сначала мы вычислим:
c1 = count_ranges(r1.begin+1, r2.end-1)
#=> count_ranges(1, 4) #=> 10
Это число диапазонов, охватываемых 1..4, ни один из которых не охватывает ни одного из NTBC. Эти 10 диапазоны 1..1, 1..2, 1..3, 1..4, 2..2, 2..3, 2..4, 3..3, 3..4 и 4..4.
Далее мы вычисляем:
c2 = count_ranges(r2.begin+1, r3.end-1)
#=> count_ranges(3, 8) #=> 21
c3 = count_ranges(r3.begin+1, r4.end-1)
#=> count_ranges(8, 12) #=> 15
c4 = count_ranges(r4.begin+1, r5.end-1)
#=> count_ranges(11, 14) #=> 10
Теперь сложим эти значения:
c1 + c2 + c3 + c4
#=> 56
Давайте сравним это с тем, что мы вычислим для итогов:
count_non_covering_ranges(n, arr)
#=> 49
Расхождение связано с тем, что у нас есть двойные счета 7 диапазонов:
c1 и c2 оба считают диапазоны 3..3, 3..4 и 4..4;c2 и c3 оба считают диапазон 8..8;и c3 и c4 оба считают диапазоны 11..11, 11..12 и 12..12.
Поэтому мы должны вычесть из 49:
count_ranges(r2.begin+1, r2.end-1) + count_ranges(r3.begin+1, r3.end-1) +
count_ranges(r4.begin+1, r4.end-1)
#=> 3 + 1 + 3 => 7
Для удобства я также вычту следующее:
count_ranges(r1.begin+1, r1.end-1) + count_ranges(r5.begin+1, r5.end-1)
#=> count_ranges(1, -1) + count_ranges(16, 14) => 0 + 0 => 0
Это разрешено, поскольку я построил count_ranges, так что count_ranges(i, j) возвращает ноль, когда j < i.