Как объединить перекрывающиеся временные диапазоны (объединение временных диапазонов)

Question

Как объединить перекрывающиеся временные диапазоны (объединение временных диапазонов)

У меня есть массив с несколькими временными диапазонами внутри:

[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]

Я хочу получить тот же массив с перекрывающимися интервалами времени, поэтому выходные данные для этого случая будут:

[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]

Таким образом, он создает новый временной диапазон, когда временные диапазоны перекрываются, и так далее. Если они не перекрываются, они будут разделены. Другой пример:

Входные данные:

[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]

Вывод (будет таким же, потому что они не перекрываются):

[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]

Я думал о некотором рекурсивном подходе, но мне нужно некоторое руководство здесь...

22

ruby-on-rails ruby

Источник

user236832 16 май '11 в 12:40

11 ответов

Решение

В поисках немного я нашел код, который делает свое дело:

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

Образец (работающий с временными диапазонами тоже!):

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

Нашел здесь: http://www.ruby-forum.com/topic/162010

5

Источник

user236832 17 май '11 в 09:38

Вы можете сделать это, используя гем multi_range.

Пример 1:

ranges = [
  Time.parse('Tue, 24 May 2011 08:00:00 CEST +02:00..Tue')..Time.parse('24 May 2011 13:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 16:30:00 CEST +02:00..Tue')..Time.parse('24 May 2011 18:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 08:00:00 CEST +02:00..Tue')..Time.parse('24 May 2011 09:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 15:30:00 CEST +02:00..Tue')..Time.parse('24 May 2011 18:00:00 CEST +02:00'),
]

MultiRange.new(ranges).merge_overlaps.ranges
# => [2011-05-24 08:00:00 +0800..2011-05-24 13:00:00 +0800, 2011-05-24 15:30:00 +0800..2011-05-24 18:00:00 +0800]

Пример 2:

ranges = [
  Time.parse('Tue, 24 May 2011 08:00:00 CEST +02:00')..Time.parse('Tue, 24 May 2011 13:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 16:00:00 CEST +02:00')..Time.parse('Tue, 24 May 2011 18:00:00 CEST +02:00'),
]

MultiRange.new(ranges).merge_overlaps.ranges
# => [2011-05-24 08:00:00 +0800..2011-05-24 13:00:00 +0800, 2011-05-24 16:00:00 +0800..2011-05-24 18:00:00 +0800]

4

Источник

user2131983 16 окт '20 в 05:58

Грань драгоценного камня имеет Range.combine метод, который может быть полезен: http://rdoc.info/github/rubyworks/facets/master/Range

2

Источник

user308448 10 июн '14 в 20:17

Решение, предлагаемое @wayne-conrad, очень хорошее. Я реализовал это для проблемы, на которую я наткнулся. Затем я реализовал итерационную версию и сравнил их. Оказывается, итеративная версия быстрее. Примечание: я использую ActiveSupport за Range#overlaps? и помощники по времени, но реализовать версию на чистом Ruby тривиально.

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)

1

Источник

user1836143 21 авг '17 в 15:01

Решение в одном методе и без ошибок, что я могу сказать:

      def merge_ranges(ranges)
  ranges = ranges.sort_by(&:first)
  merged = [ranges[0]]

  ranges.each do |current|
    previous = merged[-1]
    if current.first <= previous.last
      merged[-1] = previous.first..[previous.last, current.last].max
    else
      merged.push(current)
    end
  end

  merged
end

Использование:

      ranges = [
  Time.parse('Tue, 24 May 2011 08:00:00 CEST +02:00..Tue')..Time.parse('24 May 2011 13:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 16:30:00 CEST +02:00..Tue')..Time.parse('24 May 2011 18:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 08:00:00 CEST +02:00..Tue')..Time.parse('24 May 2011 09:00:00 CEST +02:00'),
  Time.parse('Tue, 24 May 2011 15:30:00 CEST +02:00..Tue')..Time.parse('24 May 2011 18:00:00 CEST +02:00'),
]
merge_ranges(ranges)

#=> [2011-05-24 08:00:00 +0200..2011-05-24 13:00:00 +0200, 2011-05-24 15:30:00 +0200..2011-05-24 18:00:00 +0200]

Отказ от ответственности: это порт /questions/38103938/sliyanie-pitonov-s-perekryivayuschimisya-intervalami/38103944#38103944

1

Источник

user807442 02 фев '23 в 15:36

Я внес небольшое обновление в ответ Wayne Conrad, чтобы обрабатывать крайние случаи, связанные с открытыми массивами (созданными с помощью оператора... вместо оператора..).

Я изменил имя на merge_continuous_ranges поскольку в то время как диапазон вроде 0...1 а также 1..2 не перекрываются, их объединенные диапазоны непрерывны, поэтому есть смысл их объединить:

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

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

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

  exclude_end = case a.end <=> b.end
  when -1
    b.exclude_end?
  when 0
    a.exclude_end? && b.exclude_end?
  when 1
    a.exclude_end?
  end

  exclude_end ? range_begin...range_end : range_begin..range_end
end

1

Источник

user2865270 26 окт '19 в 02:34

Какой-то алгоритм, который может помочь:

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

1

Источник

user217711 16 май '11 в 12:59

Gem range_operators делает замечательную работу, добавляя недостающие возможности в Ruby Range учебный класс. Это намного меньше, чем добавление целого камня граней.

В вашем случае решением было бы rangify метод, который добавляется к Array класс и будет делать именно то, что вы ищете.

1

Источник

user932293 24 мар '18 в 22:13

Разве вы не хотите найти наименьшее первое значение и наибольшее последнее значение из набора массивов?

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]

0

Источник

user138557 16 май '11 в 15:32

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

[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]

Состояние в ranges_overlap не обрабатывает этот вариант использования. Так я написал это

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

Это касается всех крайних случаев для меня до сих пор.

0

Источник

user706601 21 июн '16 в 12:59

Другие вопросы по тегам ruby-on-rails ruby

user238886 16 май '11 в 14:18 2011-05-16 14:18 · Accepted Answer · 2011-05-16 14:18

Учитывая функцию, которая возвращает истину, если два диапазона перекрываются:

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

(эта функция любезно предоставлена sepp2k и steenslag)

и функция, которая объединяет два перекрывающихся диапазона:

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

затем эта функция, учитывая массив диапазонов, возвращает новый массив со всеми перекрывающимися диапазонами:

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