How to build an array of intervals from other intervals

Question

Given the following array of intervals:

today = Time.current.beginning_of_day
tomorrow = Time.current.tomorrow.beginning_of_day

availabilities = {
  monday: [
    { start_time: today + 6.hours,
      end_of_time: today + 12.hours },
    { start_time: today + 8.hours,
      end_of_time: today + 18.hours }
  ],
  tuesday: [
    { start_time: tomorrow + 10.hours,
      end_time: tomorrow + 16.hours },
    { start_time: tomorrow + 18.hours,
      end_time: tomorrow + 23.hours }
  ]
}

How do I build an array of availabilitiesintervals so that, for example, in the case monday, and tuesdaythe hash:

# monday
{ start_time: 'Today at 06:00',
  end_time: 'Today at 18:00' }
# tuesday
[ { start_time: 'Tomorrow at 10:00',
    end_time: 'Tomorrow at 16:00' },
  { start_time: 'Tomorrow at 18:00',
    end_time: 'Tomorrow at 23:00' } ]

What I want to achieve is to get availability intervals for a given day no matter which entity provides that availability.

Thanks in advance, any help or guidance on using the algorithm will be greatly appreciated.

Answer 1

An algorithm for combining overlapping intervals:

1. Sort the intervals on start time
2. Assign left and right of first interval (0)
3. Iterate over the intervals from 1 to size-1
    if (current interval start lies in prev. interval)
        update right to max(prev. right, current. right) 
    else
        [left, right] is non-overlapping interval => push it to answer array
        reassign left and right to current interval
4. push last [left, right] to answer array

Decision:

# hash of overlapping intervals
availabilities = {
  monday: [
    { start_time: 6,
      end_time: 12 },
    { start_time: 8,
      end_time: 18 }
  ],
  tuesday: [
    { start_time: 10,
      end_time: 16 },
    { start_time: 18,
      end_time: 23 }
  ]
}

# function for converting hash to intervals, process, and then convert back to hash
def solve(list)
    return_hash = {}
    list.each do |key, arr|
        intervals = []
        arr.each { |hash| intervals << [hash[:start_time], hash[:end_time]] }
        non_overlapping_intervals = merge_interval(intervals)
        temp = []
        non_overlapping_intervals.each { |interval| temp << {start_time: interval[0], end_time: interval[1]} }
        return_hash[key] = temp
    end
    return_hash
end

# algorithm to merge intervals and return non-overlapping intervals
def merge_interval(v)
    intervals = []
    v.sort()
    size = v.size()
    l, r = v[0][0], v[0][1]
    (1...size).each do |i|
        if v[i][0] <= r
            r = [r,v[i][1]].max;
        else
            intervals << [l, r]
            l, r = v[i][0], v[i][1]
        end         
    end
    intervals << [l, r]
    return intervals
end

# solve call for availabilities hash
p solve(availabilities)

Output:

{
 :monday=>[{:start_time=>6, :end_time=>18}],
 :tuesday=>[{:start_time=>10, :end_time=>16},
            {:start_time=>18, :end_time=>23}]
}

Answer 2

• Sort intervals by start time
• , .
• ,
• , .

, :

A, B C , A C , , B A. .

Ruby.

def overlap?(r1, r2)
  !(r1.end <= r2.begin || r1.begin >= r2.end)
end

def merge_intervals(r1, r2)
  [r1.begin, r2.begin].min..[r1.end, r2.end].max
end

def flatten_intervals(intervals)
  first, *rest = intervals.sort_by(&:begin)
  rest.each_with_object([first]) { |r,stack| stack <<
    (overlap?(stack.last, r) ? merge_intervals(stack.pop, r) : r) }
end

intervals = [0..2, 5..8, 4..9, 11..13, 15..17, 19..21, 17..19, 16..20]
flatten_intervals(intervals)
  #=> [0..2, 4..9, 11..13, 15..21]

Answer 3

. , ( ). , , ( ).

,

time_intervals = [0..2, 5..8, 4..9, 11..13, 15..17, 19..21, 17..19, 16..20]

:

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23
xx xx xx       xx xx xx xx       xx xx xx    xx xx xx    xx xx xx
            xx xx xx xx xx xx                      xx xx xx 
                                                xx xx xx xx xx

:

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23
xx xx xx    xx xx xx xx xx xx    xx xx xx    xx xx xx xx xx xx xx xx 

.

h = 24.times.with_object({}) { |i,h| h[i] = :uncovered } 
time_intervals.each { |range|
  (range.begin..range.end).each { |i| h[i] = :covered } }
h.delete_if { |_,v| v == :uncovered }.
  keys.
  slice_when { |k1, k2| k2 - k1 > 1 }.
  map { |a| a.first..a.last }
  #=> [0..2, 4..9, 11..13, 15..21]

.

h = 24.times.with_object({}) { |i,h| h[i] = :uncovered } 
  #=> {0=>:uncovered, 1=>:uncovered, 2=>:uncovered,..., 23=>:uncovered} 
time_intervals.each { |range|
  (range.begin..range.end).each { |i| h[i] = :covered } }
h #=> { all k=>:covered except k=>:uncovered for k = 3, 10, 14, 22 and 23 } 
g = h.delete_if { |_,v| v == :uncovered }
  #=> { all k=>:covered, k = 1,2, 4,5,6,7,8,9, 11,12,13, 15,16,17,18,19,20,21v]
k = g.keys
  #=> [0, 1, 2, 4, 5, 6, 7, 8, 9, 11, 12, 13, 15, 16, 17, 18, 19, 20, 21] 
e = k.slice_when { |k1, k2| k2 - k1 > 1 }
  #=> #<Enumerator: #<Enumerator::Generator:0x007fee0a05c7b0>:each> 

, :

e.entries
  #=> [[0, 1, 2], [4, 5, 6, 7, 8, 9], [11, 12, 13], [15, 16, 17, 18, 19, 20, 21]]

See Enumerated # entries . You can also list # to_a .

The final step is to convert arrays to ranges.

e.map { |a| a.first..a.last }
  #=> [0..2, 4..9, 11..13, 15..21]

Answer 4

With a slightly different format (range instead of a hash with inconsistent keys) this problem becomes simpler:

today = 0
tomorrow = 24

availabilities = {
  monday: [
    { start_time: today + 6,
      end_time: today + 12 },
    { start_time: today + 8,
      end_time: today + 18 }
  ],
  tuesday: [
    { start_time: tomorrow + 10,
      end_time: tomorrow + 16 },
    { start_time: tomorrow + 18,
      end_time: tomorrow + 23 }
  ]
}

availabilities = availabilities.map do |day, avails|
  [ day,
    avails.map do |avail|
      (avail[:start_time]..avail[:end_time])
    end
  ]
end.to_h
# {:monday=>[6..12, 8..18], :tuesday=>[34..40, 42..47]}

Then you can use the gem range operator to sum the ranges.