Techioz Blog

同時日付を検出する方法

概要

単純に見えるアルゴリズムが必要ですが、これを行うための適切に最適化された方法がまだ思いつきません。

次の json オブジェクトがあります。

  [
        {
            "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"
        }
    ]

ご覧のとおり、2 番目のオブジェクトは最初のオブジェクトの範囲内にあります。 この配列を反復処理して、どの日付範囲が競合している（重複している）かを返す必要があります。言い換えれば、各日付範囲が他の日付範囲と重複することはありません。

例

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"
        }
    ]

私のプロジェクトは現在 Ruby on Rails で行われていますが、アルゴリズムを実装する方法のアイデアが必要なだけなので、高レベルのプログラミング言語であれば何でも良いでしょう。

何か案は？

解決策

まず、ハッシュのリストを変換して日付を Date オブジェクトに解析します。

require 'date'

dates = input.map do |hsh|
  hsh.transform_values { |str| Date.parse str }
end

これで、ネストされたループを使用して Range#cover? を使用できるようになりました。重複があるかどうかを確認するには:

conflicting = dates.select.with_index do |date, idx|
  [date[:start], date[:end]].any? do |date_to_compare|
    dates.map.with_index.any? do |date2, idx2|
      next if idx == idx2 # so we don't compare to self
      (date2[:start]..date2[:end]).cover?(date_to_compare)
    end
  end
end