# Adding intervals to an interval store

Write a program to do addition of intervals to an interval store.

An interval is represented by an array of two elements - the lower and the upper bound (you can assume integers). Assume that intervals are constructed properly (e.g. the lower bound is not greater than the upper bound, etc.).

Implement the #add method that will add a new interval, handling the merges properly.

Example:

> store = IntervalStore.new
[]
[[1, 2]]
[[1, 2], [5, 6]]
[[1, 4], [5, 6]]
[[1, 4], [5, 6]]
[[1, 6]]
[[0, 7]]


Here is my Python code. It works but is not perfect.

class IntervalStore(object):
def __init__(self):
self.store = []

def filter_result(self, flatten_store, low_index, upp_index):
useless_values = filter(lambda value: low_index < flatten_store.index(value) < upp_index, flatten_store)
flatten_store = filter(lambda value: value not in useless_values, flatten_store)
self.store = []
for i, k in zip(flatten_store[0::2], flatten_store[1::2]):
self.store.append([i, k])

flatten_store = [number for pair in self.store for number in pair]
low_index, upp_index = self.index_of(low, flatten_store), self.index_of(upp, flatten_store)

if low_index >= 0 and upp_index >= 0:
if low_index % 2 != 0:
low_index -= 1
if upp_index % 2 == 0:
upp_index += 1
elif low_index >= 0 > upp_index:
if low_index % 2 != 0:
low_index -= 1
flatten_store.append(upp)
flatten_store = sorted(flatten_store)
upp_index = self.index_of(upp, flatten_store)
if upp_index % 2 != 0:
upp_index += 1
elif low_index < 0 <= upp_index:
if upp_index % 2 == 0:
upp_index += 1
flatten_store.append(low)
flatten_store = sorted(flatten_store)
low_index = self.index_of(low, flatten_store)
if low_index % 2 != 0:
low_index -= 1
upp_index += 1
else:
flatten_store.append(low)
flatten_store.append(upp)
flatten_store = sorted(flatten_store)
low_index, upp_index = self.index_of(low, flatten_store), self.index_of(upp, flatten_store)

if low_index % 2 != 0:
low_index -= 1
if upp_index % 2 == 0:
upp_index += 1
self.filter_result(flatten_store, low_index, upp_index)

def index_of(self, value, list):
try:
return list.index(value)
except ValueError:
return -1


same as Ruby code:

class IntervalStore

def initialize
@store = []
end

def to_s
"[#{@store.map{ |i| "[#{i.first}, #{i.last}]" }.join(', ')}]"
end

# TODO - implement this method
flatten_store = @store.flatten

low_index, upp_index = flatten_store.index(low), flatten_store.index(upp)
if low_index and upp_index
low_index -=1 if low_index.odd?
upp_index +=1 if upp_index.even?
elsif low_index and !upp_index
low_index -= 1 if low_index.odd?
(flatten_store << upp).sort!
upp_index = flatten_store.index(upp)
upp_index += 1 if upp_index.odd?
elsif !low_index and upp_index
upp_index += 1 if upp_index.even?
(flatten_store << low).sort!
low_index = flatten_store.index(low)
low_index -= 1 if low_index.odd?
upp_index += 1
else
(flatten_store << low << upp).sort!
low_index, upp_index = flatten_store.index(low), flatten_store.index(upp)

low_index -= 1 if low_index.odd?
upp_index += 1 if upp_index.even?
end

filter_result = filter_store(flatten_store, low_index, upp_index)
format_result(filter_result)
end

def format_result(rest)
@store = []
rest.each_slice(2) { |pair_values| @store << pair_values }
@store
end

def filter_store(flatten_store, low_index, upp_index)
flatten_store.clone.delete_if do |value|
flatten_store_index = flatten_store.index(value)
low_index < flatten_store_index and flatten_store_index < upp_index
end
end
end


I want to know how you would do it in other ways to make it smarter.

• In the future, please consider asking about python and ruby in separate questions that mention each other. Commented Apr 6, 2014 at 18:02
• An important question would be how efficient you want this to be. Trivial implementations using arrays are pretty slow; more sofisticated solutions use interval trees (en.wikipedia.org/wiki/Interval_tree). Commented Apr 7, 2014 at 7:32
• @tokland That should be an answer! Commented Apr 11, 2014 at 22:07

Others have suggested different strategies, I'll comment on your code:

Meaningful naming
low and upp are abbreviations, which are rather ambiguous. Better call them lower_limit and upper_limit. The name of the method (add) adds to the confusion, since it is not apparent what exactly are you adding. add_interval is more descriptive.

Method names should be actions (add_XXX, format_XXX, filter_XXX), but variable names should be nouns (flattened_store instead of flatten_store). This is especially important in ruby, where the same syntax might either call a method or refer to a local variable.

The innards of your add method are quite 'magic'. For the casual reader there is no way to understand why what you do there works. A lot of .odd?s and .even?s, and += 1 and -= 1 with no rhyme or reason.
Build your solution in a way that a reader who is not familiar with it will understand what you are trying to do. Otherwise, she won't be able to maintain your code when needed. You won't be able to maintain it to in a couple of months, or even weeks.
Break it up to meaningful helper methods. Try to keep meaningful structures (if you are concerned with whether the ID is odd or even, maybe a better solution will not include flattening the store in the first place?).
If you find that you are still left with unintelligible code (and only as a last resort!) a couple of comments explaining what you are doing and why may be very helpful.

Redundant logic

• Your to_s method is totally redundant, as @store.to_s will result in exactly the same string.
• format_result could be simplified to

def format_result(rest)
@store = rest.each_slice(2).to_a
end

• .clone.delete_if could be simplified to .reject.
• filter_store as a whole could be simplified to

def filter_store(flatten_store, low_index, upp_index)
flatten_store[0..low_index] + flatten_store[high_index..-1]
end


# TODO - implement this method
I guess you already did that - you can safely delete the comment.

• All good points, Uri, and well-stated. Identifying problems and weaknesses in existing code is probably more important to learning than is the suggestion of alternatives. Commented Apr 10, 2014 at 16:09

If you have range [a,b], and want to add a range [c,d], there are 6 possible scenarios if you make the assumption, a < b, c < d

b < c - undershoot
a < c, b >= c, b <= d - left overlap
a <= c, b >= d - total overlap
a >= c, b <= d - subsection
a > c, b > d - right overlap
a > d - overshoot


The first and the last cases simply add a new range, while left/right/total overlap edit the current range... and subsection can be ignored.

My solution is to edit the function add, such that it follows this algorithm:

• 1 - look at all ranges
• 2 - if subsection found return
• 3 - if left/right/total overlap found remove the current range being evaluated from the range list, merge the two ranges, then call add with the larger range.
• 4 - if ends up being an over/under shoot for all ranges, add the range

class IntervalStore(object):
def __init__(self):
self.range_list = []
def __str__(self):
return str(self.range_list)

def __repr__(self):
return str(self)

for interval in self.range_list:
if interval[0] <= low and interval[1] >= high:
return
if interval[0] > high or interval[1] < low:
continue
else:
self.range_list.remove(interval)
return
if len(self.range_list) == 0:
self.range_list.append( [low, high])
else:
insert_index = 0
while insert_index < len(self.range_list) and high > self.range_list[insert_index][0]:
insert_index += 1
self.range_list.insert(insert_index, [low, high])


EDIT If you wanted to avoid an error regarding low > high input, then add low, high = sorted([low,high]) at the beginning of the add function.

Also add if low == high: return

• Good analysis! However, I wouldn't do the if low==high: return thing because it could be used for single element : [i, i] = {i}. Also, if i were you I'd write the inside of the loop without a continue as it seems quite easy to do. Commented Apr 6, 2014 at 21:49
• @Josay I would interpret a single element i is captured in range [ i , i+1] because the delata (i +1) - i = 1 Commented Apr 6, 2014 at 23:32

I'll stick to the ruby code, as python isn't my strong suit. But I imagine it wouldn't take much to make the approach below more pythonic.

There is a lot going on that #add method. A lot more than there needs to be. I'd create a more specific Interval class to go along with IntervalStore.

I'd subclass Range to model the intervals, and give that subclass some methods that let's it check for overlaps and performs the merging. Subclassing Array is also an option, but Range has a couple of useful methods already, and besides, it's defined by its upper and lower bounds - like an interval. Only thing to note is that Range objects are immutable, so any merging will have to return a new instance, rather than modify an existing one.

This will make the IntervalStore class a lot simpler, now that can deal with objects that know what they are.

For there, the steps when adding a new interval are:

1. Appending: Push the interval to the internal array
2. Sorting: Sort the array
3. Coalescing: Loop through and check if two consecutive intervals can be merged into one

Based on all that, I get this Interval class:

class Interval < Range
# Check if another interval overlaps this one
def overlap?(other)
cover?(other.min) || cover?(other.max)
end

# Return a new Interval by merging this one with another
def merge(other)
Interval.new([min, other.min].min, [max, other.max].max)
end

# Simplified array representation
def to_a
[min, max]
end
end


And for IntervalStore:

class IntervalStore
def initialize
@intervals = []
end

@intervals.push(Interval.new(min, max))
@intervals.sort_by!(&:min)
@intervals = @intervals.inject([]) do |merged, interval|
if merged.any? && merged.last.overlap?(interval)
merged << merged.pop.merge(interval)
else
merged << interval
end
end
end

# Returns an array representation
def to_a
@intervals.map(&:to_a)
end
end


And bingo.

Update: If you want a solution that's true to the very letter of the task, here's one:

class IntervalStore < Array
def initialize
super
end

push([low, high])
sort_by!(&:first)
collapse
end

private

def collapse
collapsed = inject([]) do |merged, interval|
can_merge = merged.any? && overlap?(merged.last, interval)
merged << (can_merge ? merge(merged.pop, interval) : interval)
end
clear.concat(collapsed)
end

def overlap?(a, b)
a = Range.new(*a) # just for the cover? method
a.cover?(b.first) || a.cover?(b.last)
end

def merge(a, b)
[ [a.first, b.first].min , [a.last, b.last].max ]
end
end


Personally, I don't like it quite as much, apart from its conciseness. I'm subclassing Array to have IntervalStore exactly match the "output" in the task (just for the heck of it), but I wouldn't recommend that - it's an array now, so if you call, say, flatten! on it, everything screws up. The class now also contains a few non-OOPish functions that don't operate on self in any way.

But all that aside, the point is that you literally get this:

store = IntervalStore.new # => []
store.add(1, 2) # => [[1, 2]]
store.add(5, 6) # => [[1, 2], [5, 6]]
store.add(1, 4) # => [[1, 4], [5, 6]]
store.add(1, 2) # => [[1, 4], [5, 6]]
store.add(3, 5) # => [[1, 6]]
store.add(0, 7) # => [[0, 7]]


Here is another way of doing it. (I have omitted comments on your code because I have nothing to add to @Uri's excellent answer.)

Code

First define an Interval class. This allows us to keep intervals as single objects in the main class, without having to fuss much with end points of intervals.

class Interval

def initialize(left,right)
@left = left
@right = right
end

# Is self entirely to the left of other?
def < (other)
self.right < other.left
end

# Is self entirely to the right of other?
def > (other)
self.left > other.right
end

# Return the lessor of the left end of self and the left end of other
def left_most(other)
[self.left, other.left].min
end

# Return the greater of the right end of self and the right end of other
def right_most(other)
[self.right, other.right].max
end

# How intervals are to be displayed
def inspect
"#{self.left}..#{self.right}"
end
end


The main class:

class IntervalStore

def initialize
# Array to hold Interval objects
@intervals = []
end

# Create an Interval object

if @intervals.empty?
return
end

# intervals in @intervals entirely to the left of interval_to_add
before = @intervals.find_all {|i| i < interval_to_add }
# intervals in @intervals entirely to the right of interval_to_add
after  = @intervals.find_all {|i| i > interval_to_add }

# We will replace all intervals between the before and after
# intervals (if any) with an interval new_interval

if  ([email protected] || [email protected])
# Case where all intervals are to the left of interval_to_add or to the
else
# before.size is the offset of the left-most interval in @intervals
# that is not in before
# @intervals.size-after.size-1 is the offset of the right-most
# interval in @intervals that is not in after
end
@intervals = before + [new_interval] + after
end
end


Notice that this approach keeps the intervals in sorted order.

Example

is = IntervalStore.new

• Nice solution, I would consider renaming the variables though, as int is a loaded name, and can be confusing when talking about intervals of ints... Commented Apr 18, 2014 at 19:28
• Good suggestion, @Uri. I changed all the int's to interval. Thanks. Commented Apr 18, 2014 at 20:03