如何检测并发日期

Question

我需要一个看起来很简单的算法，但我仍然想不出一个很好的优化方法来做到这一点。

我有以下 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"
        }
    ]

如您所见，第二个对象在第一个对象的范围内。 我需要遍历这个数组，return哪些日期有冲突。

我的项目现在在 rails 的 ruby 中，但我只需要了解如何实现该算法，任何高级编程语言都可以。

有什么想法吗？

Answer 1

这些字符串看起来像 ISO 8601 格式。您应该能够轻松地将其解析为 Date/DateTime/orsimilar 对象。查看关于那些类的文档，它会在那里显示，告诉你 cn 这样做。然后，在解析为对象之后，您应该能够简单地使用 =/> 运算符比较这些日期对象。有了这个，您将能够比较 starts/ends，并且您将能够确定日期 X 是否为：

(a) 完全在另一个之前
(b) startbefore and ends within the another
(c) 完全在另一个里面
(d) startswithin 并在另一个之后结束
(e) 完全在另一个之后
(f) 更长并且完全包含另一个

我认为这就是所有可能性，但您最好 double-check。如果需要的话，把它们都画在时间轴上，看看有没有其他的可能性。

当您拥有可以执行此分类的代码时，您就可以开始实施基于该分类的其余逻辑。

but I still can't think about a well optimised way

不要。以任何方式首先编写它，只是为了让它工作和可靠。把问题从头到尾理解透彻。然后测量它的速度和质量。如果不好，则根据 first-whatever-guess 关于 speed/quality 的观察编写一个 v2 版本。测量和比较。如果仍然不好，则收集代码、数据集、测量，确保测试用例和测量对于没有您的计算机、网络和密码等的读者是可重复的，然后解释问题以及如何 fix/optimize。如果没有所有这些，询问“优化”*) 主要会导致纯粹的猜测。

*) OFC 假设“优化良好的方式”不是一个空洞的流行语，而是一个真正的性能问题

Answer 2

首先，我们可以转换哈希列表以将日期解析为 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

Answer 3

使用日期字段上的 BTREE 索引将数据推送到数据库中。让数据库为您完成工作。

假设我们有以下 table:

TABLE myDate {
    id BIGINT UNSIGNED, date_start DATETIME, date_end DATETIME
}

那么你想要 date_start 和 date_end 上的 BTREE（或 BTREE+）索引，以及 id 上的 HASH 索引。

这些就位后，为您的 table 提供数据，并执行以下 select 语句以查找重叠的时间：

-- Query to select dates that are fully contained such as in the example (l contains r):
SELECT l.id, l.date_start, l.date_end, r.id, r.date_start, r.date_end
FROM myDate l JOIN myDate r ON (l.date_start < r.date_start) AND (l.date_end > r.date_end);

-- Query to select dates that overlap on one side:
SELECT l.id, l.date_start, l.date_end, r.id, r.date_start, r.date_end
FROM myDate l JOIN myDate r ON ((l.date_start < r.date_start) AND (l.date_end > r.date_start)) OR ((l.date_start > r.date_start) AND (l.date_end < r.date_start));

Answer 4

检测范围覆盖的 DateTime 对象

可能有更优雅的方法来执行此操作，但这对我来说似乎相对简单。诀窍是将您的哈希值转换为 DateTime ranges that can take advantage of the built-in Range#cover? 方法。

考虑以下几点：

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

因为范围#cover？是布尔值，您可能更愿意简单地存储涵盖的日期并在以后对它们做一些事情，而不是立即对每个日期采取行动。在那种情况下，只需使用 Array#select。例如：

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

如何检测并发日期

How to detect concurrent dates

ruby

arrays

algorithm

date

date-range

检测范围覆盖的 DateTime 对象