How to detect concurrent dates

Question

I need an algorithm which looks simple, but I still can't think about a well optimised way to do to do this.

I have the following json object:

  [
        {
            "start": "2000-01-01T04:00:00.000Z",
            "end": "2020-01-01T08:00:00.000Z"
        }, {
            "start": "2000-01-01T05:00:00.000Z",
            "end": "2020-01-01T07:00:00.000Z"
        }
    ]

As you can see, the second object is inside the range of the first. **I need to iterate over this array and return which date ranges are conflicting(overlaping). In other words: each date range could never overlap one of the others. **

Example

overlaping date ranges
 [
        {
            "start": "2000-01-01T04:00:00.000Z",
            "end": "2020-01-01T08:00:00.000Z"
        }, 
       {
            "start": "2010-01-01T05:00:00.000Z",
            "end": "2020-01-01T07:00:00.000Z"
        },
       {
            "start": "2010-01-01T05:00:00.000Z",
            "end": "2020-01-01T07:00:00.000Z"
        }
    ]

No overlaping dates
 [
        {
            "start": "2000-01-01T04:00:00.000Z",
            "end": "2001-01-01T08:00:00.000Z"
        }, 
       {
            "start": "2002-01-01T05:00:00.000Z",
            "end": "2003-01-01T07:00:00.000Z"
        },
       {
            "start": "2010-01-01T05:00:00.000Z",
            "end": "2020-01-01T07:00:00.000Z"
        }
    ]

My project is in ruby on rails right now, but I just need an idea how to implement the algorithm so, any high level programming language would be good.

Any ideas?

Answer 1

Detect a DateTime Object Covered By a Range

There may be a more elegant way to do this, but this seems relatively straightforward to me. The trick is to convert your Hash values into DateTime ranges that can take advantage of the built-in Range#cover? method.

Consider the following:

require 'date'

dates = [
  {:start=>"2000-01-01T04:00:00.000Z", :end=>"2020-01-01T08:00:00.000Z"},
  {:start=>"2000-01-01T05:00:00.000Z", :end=>"2020-01-01T07:00:00.000Z"},
]

# convert your date hashes into an array of date ranges
date_ranges = dates.map { |hash| hash.values}.map do |array|
  (DateTime.parse(array.first) .. DateTime.parse(array.last))
end

# compare sets of dates; report when the first covers the second range
date_ranges.each_slice(2) do |range1, range2|
  puts "#{range1} covers #{range2}" if range1.cover? range2
end

Because Range#cover? is Boolean, you might prefer to simply store dates which are covered and do something with them later, rather than taking immediate action on each one. In that case, just use Array#select. For example:

date_ranges.each_slice(2).select { |r1, r2| r1.cover? r2 }