Fork me on GitHub

Project Notes

Reducing Overlapping Ranges

Looking at solutions for how to aggregate a series of ranges while excluding any overlaps (e.g. set of date ranges)

Notes

Here’s the essential problem: given a set of ranges, calculate the net range coverage, excluding any overlap or duplication. The specific case I have in mind is a set of date ranges and I need to calculate the total duration without duplication/double counting.

The Ruby Range class offers some tantilizing functions such as cover?, and Rails adds some spice e.g. overlaps?, but they don’t get much closer to the goal.

Overlap of a date with an array of date intervals from stackoverflow is getting closer, and gave me a pointer to the range_operators that looks promising.

A Naïve Algorithm

Here’s the thinking:

  • the data pairs are sorted by their first element
  • then each subsquent pair will fall into one of three cases:
    • start after the last end item, so can be added to the result in full
    • end after the last end item, so the difference between the last end and the “new” end is added to the result
    • end before the end of the last item, so can be ignored (already covered)

And here’s the implementation I used:

  def naive_calculation(data)
    data.sort_by { |pair| pair.first }.each_with_object(
      { duration: 0, last_end: 0 }
    ) do |pair, memo|
      if pair.first > memo[:last_end]
        memo[:duration] += pair.last - pair.first + 1
        memo[:last_end] = pair.last
      elsif pair.last > memo[:last_end]
        memo[:duration] += pair.last - memo[:last_end]
        memo[:last_end] = pair.last
      end
    end[:duration]
  end

This passes all the test cases I’ve thrown at it so far, and actually turns out to be relatively straight-forward.

Using the Range Operators Gem

The range_operators gem offers a very useful method for this problem: rangify. It reduces a set of ranges down to the smallest set of non-overlapping ranges. e.g.

[5..10, 8..12, 6..8, 20..22].rangify
 => [5..12, 20..22]

So here’s the equivalent algorithm. The rangify call is the core, surrounded:

  • pre: convert the 2-D array into an array of ranges
  • post: sum the sizes of the resulting ranges
  def range_operators_calculation(data)
    data.map do |pair|
      Range.new *pair
    end.rangify.collect(&:size).sum
  end

Test Run

See examples.rb for the implementation of both the naïve and range operators versions, tested with a couple of different datasets. Executing the file runs the test suite:

$ ./examples.rb
Run options: --seed 32192

# Running:

....

Finished in 0.001889s, 2117.5228 runs/s, 2117.5228 assertions/s.

4 runs, 4 assertions, 0 failures, 0 errors, 0 skips

Credits and References

About LCK#152 ruby
Project Source on GitHub Return to the Project Catalog

This page is a web-friendly rendering of my project notes shared in the LittleCodingKata GitHub repository.

LittleCodingKata is my collection of programming exercises, research and code toys broadly spanning things that relate to programming and software development (languages, frameworks and tools).

These range from the trivial to the complex and serious. Many are inspired by existing work and I'll note credits and references where applicable. The focus is quite scattered, as I variously work on things new and important in the moment, or go back to revisit things from the past.

This is primarily a personal collection for my own edification and learning, but anyone who stumbles by is welcome to borrow, steal or reference the work here. And if you spot errors or issues I'd really appreciate some feedback - create an issue, send me an email or even send a pull-request.