ruby on rails - unir - Cómo combinar rangos de tiempo superpuestos(rangos de tiempo de unión)

unir nombres y apellidos en excel

Question

Tengo una matriz con varios rangos de tiempo dentro:

[Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00,
Tue, 24 May 2011 16:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00,
Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 09:00:00 CEST +02:00,
Tue, 24 May 2011 15:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00]

Quiero obtener la misma matriz con los rangos de tiempo superpuestos combinados, por lo que la salida para este caso será:

[Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00,
Tue, 24 May 2011 15:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00]

Así que crea un nuevo intervalo de tiempo cuando los intervalos de tiempo se superponen, y así sucesivamente. Si no se superponen se mantendrán separados. Otro ejemplo:

Entrada:

[Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00,
Tue, 24 May 2011 16:00:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00]

Salida (será la misma porque no se superponen):

[Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00,
Tue, 24 May 2011 16:00:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00]

Estaba pensando en un enfoque recursivo, pero necesito una guía aquí ...

Answer 1

¿No solo desea buscar el primer valor más pequeño y el último último valor más grande del conjunto de matrices?

ranges = [Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 13:00:00 CEST +02:00,
Tue, 24 May 2011 16:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00,
Tue, 24 May 2011 08:00:00 CEST +02:00..Tue, 24 May 2011 09:00:00 CEST +02:00,
Tue, 24 May 2011 15:30:00 CEST +02:00..Tue, 24 May 2011 18:00:00 CEST +02:00]
union = [ranges.collect(&:first).sort.first, ranges.collect(&:last).sort.last]

Answer 2

Algún tipo de algoritmo que podría ayudar:

Sort range array by start time (r1, r2, r3, r4, .. rn)
for each range pair [r1, r2], [r2, r3] .. [rn-1, rn]:
if r1_end > r2_start: # they overlap
add [r1_start, r2_end] to new range array
else: # they do not overlap
add [r1] and [r2] to new range array (no changes)
startover with the new range array until no more changes

Answer 3

Buscando un poco he encontrado un código que hace el truco:

def self.merge_ranges(ranges)
ranges = ranges.sort_by {|r| r.first }
*outages = ranges.shift
ranges.each do |r|
lastr = outages[-1]
if lastr.last >= r.first - 1
outages[-1] = lastr.first..[r.last, lastr.last].max
else
outages.push(r)
end
end
outages
end

Una muestra (¡trabajando con rangos de tiempo también!):

ranges = [1..5, 20..20, 4..11, 40..45, 39..50]
merge_ranges(ranges)
=> [1..11, 20..20, 39..50]

Se encuentra aquí: http://www.ruby-forum.com/topic/162010

Answer 4

Dada una función que devuelve truey si dos rangos se superponen:

def ranges_overlap?(a, b)
a.include?(b.begin) || b.include?(a.begin)
end

(Esta función es cortesía de sepp2k y steenslag )

y una función que combina dos rangos superpuestos:

def merge_ranges(a, b)
[a.begin, b.begin].min..[a.end, b.end].max
end

entonces esta función, dada una matriz de rangos, devuelve una nueva matriz con todos los rangos superpuestos combinados:

def merge_overlapping_ranges(overlapping_ranges)
overlapping_ranges.sort_by(&:begin).inject([]) do |ranges, range|
if !ranges.empty? && ranges_overlap?(ranges.last, range)
ranges[0...-1] + [merge_ranges(ranges.last, range)]
else
ranges + [range]
end
end
end

Answer 5

El gem range_operators hace un trabajo maravilloso al agregar características faltantes a la clase Ruby Range . Es mucho más pequeño que agregar la gema completa de facets .

En su caso, la solución sería el método rangify , que se agrega a la clase Array y haría exactamente lo que está buscando.

Answer 6

La gema de facetas tiene Range.combine método Range.combine que puede ser útil: http://rdoc.info/github/rubyworks/facets/master/Range#combine-instance_method

Answer 7

La respuesta marcada funciona bien, excepto en algunos casos de uso. Uno de tales casos de uso es

[Tue, 21 June 13:30:00 GMT +0:00..Tue, 21 June 15:30:00 GMT +00:00,
Tue, 21 June 14:30:00 GMT +0:00..Tue, 21 June 15:30:00 GMT +00:00]

La condición en ranges_overlap no maneja este caso de uso. Así que escribí esto

def ranges_overlap?(a, b)
a.include?(b.begin) || b.include?(a.begin) || a.include?(b.end) || b.include?(a.end)|| (a.begin < b.begin && a.end >= b.end) || (a.begin >= b.begin && a.end < b.end)
end

Esto está manejando todos los casos de borde para mí hasta ahora.

Answer 8

La solución ofrecida por @ wayne-conrad es muy buena. Lo implementé por un problema, me topé. Luego implementé una versión iterativa y comparé las dos. Aparece, la versión iterativa es más rápida. Nota: uso ActiveSupport para ActiveSupport de Range#overlaps? y los ayudantes del tiempo, pero es trivial implementar una versión de Ruby puro.

require ''active_support/all''
module RangesUnifier
extend self
# ranges is an array of ranges, e.g. [1..5, 2..6]
def iterative_call(ranges)
ranges.sort_by(&:begin).reduce([ranges.first]) do |merged_ranges, range|
if merged_ranges.last.overlaps?(range)
merged_ranges[0...-1] << merge_ranges(merged_ranges.last, range)
else
merged_ranges << range
end
end
end
def recursive_call(ranges)
return ranges if ranges.size == 1
if ranges[0].overlaps?(ranges[1])
recursive_call [merge_ranges(ranges[0], ranges[1]), *ranges[2..-1]]
else
[ranges[0], *recursive_call(ranges[1..-1])]
end
end
def merge_ranges(a, b)
[a.begin, b.begin].min..[a.end, b.end].max
end
end
five_hours_ago = 5.hours.ago
four_hours_ago = 4.hours.ago
three_hours_ago = 3.hours.ago
two_hours_ago = 2.hours.ago
one_hour_ago = 1.hour.ago
one_hour_from_now = 1.hour.from_now
two_hours_from_now = 2.hours.from_now
three_hours_from_now = 3.hours.from_now
four_hours_from_now = 4.hours.from_now
five_hours_from_now = 5.hours.from_now
input = [
five_hours_ago..four_hours_ago,
three_hours_ago..two_hours_from_now,
one_hour_ago..one_hour_from_now,
one_hour_from_now..three_hours_from_now,
four_hours_from_now..five_hours_from_now
]
RangesUnifier.iterative_call(input)
#=> [
# 2017-08-21 12:50:50 +0300..2017-08-21 13:50:50 +0300,
# 2017-08-21 14:50:50 +0300..2017-08-21 20:50:50 +0300,
# 2017-08-21 21:50:50 +0300..2017-08-21 22:50:50 +0300
# ]
RangesUnifier.recursive_call(input)
#=> [
# 2017-08-21 12:50:50 +0300..2017-08-21 13:50:50 +0300,
# 2017-08-21 14:50:50 +0300..2017-08-21 20:50:50 +0300,
# 2017-08-21 21:50:50 +0300..2017-08-21 22:50:50 +0300
# ]
n = 100_000
Benchmark.bm do |x|
x.report(''iterative'') { n.times { RangesUnifier.iterative_call(input) } }
x.report(''recursive'') { n.times { RangesUnifier.recursive_call(input) } }
end
# =>
# user system total real
# iterative 0.970000 0.000000 0.970000 ( 0.979549)
# recursive 0.540000 0.010000 0.550000 ( 0.546755)