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

Question

我有一组持续时间(使用 moment-range 但很乐意使用 native 代码或其他东西)，如下所示:

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

简单的算法是:

1. 创建集合中 3(或 X)个不同范围的所有组合。
2. 对于每个组合，计算三者的交集。
3. 返回交集的并集。

---

// 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)

---

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