How can I get the count of overlapping ranges in sorted order?

Question

Suppose I have an array of sorted inclusive ranges:

a = [1012..1014, 1016..1020, 1017..1022, 1021..1035, 1040..1080]

I want as output an array of arrays, each of whose first element is a range and second element its overlapping count, like this:

[[1012..1014, 1], [1016..1016, 1], [1017..1020, 2], [1021..1022, 2], [1023..1035, 1], [1040..1080, 1]]

For example, the range 1017..1020 is included in two ranges 1016..1020 and 1017..1022, so its count would be two.

Answer 1

Code

require 'set'

def range_info(a)
  covered_by = a.each_with_object(Hash.new { |h,k| h[k]=Set.new }) { |r,h|
    r.each { |n| h[n] << r } }
  a.flat_map { |r| r.to_a }.
    uniq.
    slice_when { |b,c| c > b+1 }.
    flat_map { |r| r.to_a.slice_when { |b,c| covered_by[b] != covered_by[c] } }.
    flat_map { |enum| enum.to_a.map { |a| [a.first..a.last, covered_by[a.first].size] } }
end

Example

a = [1012..1014, 1016..1020, 1017..1022, 1021..1035, 1040..1080]

range_info(a)
  #=> [[1012..1014, 1], [1016..1016, 1], [1017..1020, 2], [1021..1022, 2],
  #    [1023..1035, 1], [1040..1080, 1]] 

Explanation

First create the hash covered_by with keys equal to numbers that are covered by at least one range in a, where covered_by[n] equals the set of all ranges in a that cover key n:

covered_by = a.each_with_object(Hash.new { |h,k| h[k]=Set.new }) { |r,h|
  r.each { |n| h[n] << r } }
  #=> {1012=>#<Set: {1012..1014}>, 1013=>#<Set: {1012..1014}>,
  #    ...
  #    1016=>#<Set: {1016..1020}>, 1017=>#<Set: {1016..1020, 1017..1022}>,
  #    ...
  #    1079=>#<Set: {1040..1080}>, 1080=>#<Set: {1040..1080}>} 

See my answer here for an explanation of Hash.new { |h,k| h[k]=[] }, which is similar to Hash.new { |h,k| h[k]=Set.new }.

Next, obtain an array of increasing non-overlapping ranges that cover the same numbers that are covered by one or more ranges in a:

arr = a.flat_map { |r| r.to_a }.uniq.slice_when { |b,c| c > b+1 }
  #=> [1012..1014, 1016..1035, 1040..1080] 

Next, break each of the ranges in arr into enumerators that will generate arrays of consecutive numbers that are covered by the same ranges in a:

b = arr.flat_map { |r| r.to_a.slice_when { |b,c| covered_by[b] != covered_by[c] } }
  #=> [#<Enumerator: #<Enumerator::Generator:0x007fd1ea854558>:each>,
  #    #<Enumerator: #<Enumerator::Generator:0x007fd1ea8543c8>:each>,
  #    #<Enumerator: #<Enumerator::Generator:0x007fd1ea854238>:each>] 

We can see the elements of b by converting them to arrays:

b.map(&:to_a)
  #=> [[[1012, 1013, 1014]],
  #    [[1016], [1017, 1018, 1019, 1020], [1021, 1022],
  #     [1023, 1024, 1025, 1026, 1027, 1028, 1029, 1030, 1031, 1032, 1033,
  #      1034, 1035]],
  #    [[1040, 1041, 1042, 1043, 1044, 1045, 1046, 1047, 1048, 1049, 1050,
  #      1051, 1052, 1053, 1054, 1055, 1056, 1057, 1058, 1059, 1060, 1061,
  #      1062, 1063, 1064, 1065, 1066, 1067, 1068, 1069, 1070, 1071, 1072,
  #      1073, 1074, 1075, 1076, 1077, 1078, 1079, 1080]]] 

Lastly, flat_map these arrays to arrays containing a range and the number of ranges in a that cover all the elements of the range:

c = b.flat_map { |enum| enum.to_a.map { |a| [a.first..a.last, covered_by[a.first].size] } }
  #=> [[1012..1014, 1], [1016..1016, 1], [1017..1020, 2], [1021..1022, 2],
  #    [1023..1035, 1], [1040..1080, 1]]