时间戳

首页 > 解决方案 > 如何良好有效地计算多个间隔之间的总重叠？

algorithm - 如何良好有效地计算多个间隔之间的总重叠？

问题描述

我有两个时间窗口：白天每天从 07:00 持续到 19:00，夜间从每天 19:00 持续到 7:00。然后我有给定开始和结束时间的“维护间隔”，[s，e]。s 和 e 是实数，表示从第一天午夜开始的小时数。对于任何维护间隔，我想确定是白天的最大部分还是夜间的最大部分。

因此，我开始尝试确定维护间隔在白天的总时间和维护间隔在夜间的总时间，但我不知道如何很好地做到这一点。

一些输入和输出：

  1. [20, 22] = 夜间 2 小时，白天 0 小时（因此这被归类为夜间维护间隔）
  2. [10, 25] = 白天 9 小时，夜间 6 小时（白天维护间隔）
  3. [10, 49] = 白天 21 小时，夜间 18 小时（白天维护间隔）

还要观察 2 和 3 之间的相似性。第三个间隔持续的时间要长得多（比第二个长一天），但结果是一样的。一个不错的解决方案可能会受益于这个特性，丢弃与最终解决方案无关的所有“中间的一整天”。

最好，我得到一个优雅的解决方案，可以很容易地以数学符号（而不是整个算法）显示。

希望任何人都可以提供帮助！

标签： algorithmmathtimeintervalsoverlap

解决方案

开始总是标准化，但结束需要标准化 - 只需在开始后减去一整天。现在 e 不超过 48

e = e - ((e - s) div 24) * 24

现在我们有 s 的三个变体和每个变体的三个可能的 e 范围：

 s    0..7                 7..19                   19..24
     -----------------------------------------------------
 e    s..7                 s..19                   s..31
      7..19                19..31                  31..43 
      19..s+24 (<31)       31..s+24 (<43)          43..s+24 (<48)

制作 if 条件并不难 - 长但易于阅读 

d = 0
n = 0
if s <= 7:
    if e <= 7:
       n += e - s
    elif e <= 19:
       n += 7 - s
       d += e - 7
    else   
       n += 7 - s + e - 19
       d += 12
 elif s <= 19:
    if e <= 19:
       d += e - s
    elif e <= 31:
       d += 19 - s
       n += e - 19
    else   
       d += 19 - s + e - 31
       n += 12
 else
    if e <= 31:
       n += e - s
    elif e <= 43:
       n += 31 - s
       d += e - 31
    else   
       n += 31 - s + e - 43
       d += 12

现在挤压类似的动作（未彻底检查）：

nd = [0, 0]     # night and day hours
halfdays = (s + 5) // 12   
# 0 for the 1st variant, 1 for the 2nd, 2 for the 3rd

halfhours =  halfdays * 12   #time shift
s -= halfhours
e -= halfhours

cur = halfdays & 1
next = 1 - cur
if e <= 7:
       nd[cur] += e - s
    elif e <= 19:
       nd[cur] += 7 - s
       nd[next] += e - 7
    else   
       nd[cur] += e - s - 12
       nd[next] += 12

推荐阅读