代码之家 › 专栏 › 技术社区 › cubabit

如何在一组时间段中找到常见的重叠?

duration momentjs node.js javascript

1

cubabit · 技术社区 · 8 年前

我有一组持续时间(使用 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

我花了很长时间试图解决这个问题,特别是使用 力矩范围 ,但我完全糊涂了!

更新

鉴于这一问题被否决,我认为这是因为根据堆栈溢出建议“不清楚、太宽泛或其他方面存在问题,无法以回答者可以适当解决的方式确定问题”,我想分享我所做的努力。

我遍历了所有的范围,计算出了与其他范围的重叠,但我看不出这一系列新的范围是如何帮助我的。
在@ HO2A的建议中,我试图找出范围与其他范围重叠至少3次的范围,但我认为这是我问题的症结所在。我不知道怎么做。

1 回复 | 直到 8 年前

1

hon2a 8 年前

微不足道的算法是:

从集合中创建3(或x)个不同范围的所有组合。
对于每个组合,计算三者的交集。
返回交叉点的并集。

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

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