如何找到一组持续时间中的常见重叠？

Question

我有一组持续时间（使用 moment-range 但乐于使用本机代码或其他东西），如下所示：

2018-06-19T09:00:00Z - 2018-06-19T10:00:00Z
2018-06-19T09:30:00Z - 2018-06-19T10:30:00Z
2018-06-19T09:30:00Z - 2018-06-19T11:00:00Z
2018-06-19T10:00:00Z - 2018-06-19T11:00:00Z

看起来像：

09:00 ..+-+.................
        | |
09:30 ..| |..+-+..+-+.......
        | |  | |  | |
10:00 ..+-+..| |..| |..+-+..
             | |  | |  | |
10:30 .......+-+..| |..| |..
                  | |  | |
11:00 ............+-+..+-+..

而且我想要一种算法来找到至少 3（或 x）个持续时间重叠的持续时间。在上面的示例中，有两个持续时间满足此条件：

2018-06-19T09:30:00Z - 2018-06-19T10:00:00Z
2018-06-19T10:00:00Z - 2018-06-19T10:30:00Z

我花了很长时间试图解决这个问题，尤其是使用 moment-range，但我完全不知所措！

更新

看到这个问题被否决了，我认为这是因为根据 Stack Overflow 的建议“[它] 不清楚，太宽泛，或者以其他方式识别问题，以回答者可以正确解决的方式存在问题” ，我想分享我的尝试。

我遍历了所有范围并找出了与其他范围的重叠部分，但我看不出这组新范围对我有何帮助。
根据@hon2a 的建议，我尝试计算出与其他范围重叠至少 3 次的范围，但我认为这是我问题的症结所在。我不知道该怎么做。

Answer 1

简单的算法是：

创建集合中 3（或 X）个不同范围的所有组合。
对于每个组合，计算三者的交集。
Return 交集的并集。

// ranges: Array<{ from: number, to: number }>, x: number
const combinations = _.combinations(ranges, x) // lodash.combinations
const intersections = combinations.map(combination => combination.reduce(
  (intersection, range) => ({
    from: Math.max(intersection.from, range.from),
    to: Math.min(intersection.to, range.to)
  })
  { from: Number.MIN_SAFE_INTEGER, to: Number.MAX_SAFE_INTEGER }
)).filter(({ from, to }) => from < to)
// ... (union is trivial too)

我不知道是否可以用较低的时间复杂度来完成，但由于你没有分享任何你实际尝试过的信息，我想我应该投票结束而不是回答。

如何找到一组持续时间中的常见重叠？

How can I find the common overlaps in a set of time durations?

javascript

duration

node.js

momentjs