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

Question

我有两个时间windows：白天是每天07:00到19:00，晚上是每天19:00到7:00。然后我有 'maintenance intervals' 给定的开始和结束时间 [s,e]。 s 和 e 是实数，表示从第一天午夜开始的小时数。对于任何维护间隔，我想确定它是白天的大部分时间还是夜间的大部分时间。

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

一些输入和输出：

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

还要观察 2 和 3 之间的相似性。第 3 个间隔持续的时间更长（正好比第 2 个长一天），但结果是一样的。一个好的解决方案可能会受益于此特性，丢弃所有对最终解决方案无关紧要的 'whole days in between'。

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

希望大家帮帮忙！

Answer 1

开始总是规范化，但结束需要规范化 - 只需减去开始后的完整天数。现在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

Answer 2

这可能比效率更好。除非一个间隔持续数年，否则您无需担心效率，甚至在那种情况下甚至不必担心。

让我们先声明一些名字好听的常量。我的代码是 Java，但应该不难翻译成您选择的编程语言。

private static int HOURS_PER_DAY = 24;
private static double DAY_BEGINS = 7; 
private static double NIGHT_BEGINS = 19;

现在我的算法是这样的：

    // Maintenance interval to calculate;
    // numbers are numbers of hours since start of the day where the shift begins
    double start = 10;
    double end = 49;

    if (start < 0 || start >= 24 || end < start) {
        throw new IllegalStateException();
    }

    double nightHours = 0;
    double dayHours = 0;
    double time = start;
    double nextNightBegins = NIGHT_BEGINS;
    double nextDayBegins = DAY_BEGINS;
    if (time >= DAY_BEGINS) {
        nextDayBegins += HOURS_PER_DAY;
        if (time < NIGHT_BEGINS) { // time is in day time
            // establish loop invariant
            dayHours += NIGHT_BEGINS - time;
            time = NIGHT_BEGINS;
        }
        nextNightBegins += HOURS_PER_DAY;
    }
    // Loop invariant:
    // time <= nextDayBegins < nextNightBegins || time == end.
    // Hours up to time have been summed into dayHours and nightHours.
    while (time < end) {
        assert time <= nextDayBegins : "" + time + " >= " + nextDayBegins;
        assert nextDayBegins < nextNightBegins;
        double nightHoursUntil = Math.min(nextDayBegins, end);
        nightHours += nightHoursUntil - time;
        time = nightHoursUntil;
        nextDayBegins += HOURS_PER_DAY;
        if (time < end) {
            double dayHoursUntil = Math.min(nextNightBegins, end);
            dayHours += dayHoursUntil - time;
            time = dayHoursUntil;
            nextNightBegins += HOURS_PER_DAY;
        }
    }
    assert time == end;

    System.out.format(Locale.ENGLISH,
            "%.2f hours during nighttime, %.2f hours during daytime%n",
            nightHours, dayHours);
    if (nightHours > dayHours) {
        System.out.println("Nighttime maintenance interval)");
    } else if (nightHours < dayHours) {
        System.out.println("Daytime maintenance interval");
    } else { // they are equal
        System.out.println("Undecided maintenance interval)");
    }

代码的输出是：

18.00 hours during nighttime, 21.00 hours during daytime
Daytime maintenance interval

我更喜欢而不是利用这样一个事实，即白天和黑夜的长度相等（每个 12 小时）。某天进行了更改，因此夜晚从 18:30 开始，您不想冒险让您的程序在那时默认开始发出不正确的分类。在我上面的算法中，您可以更改常量（在示例中从 19 更改为 18.5），代码仍然有效。

我确实考虑过使用 Java 的 LocalTime，但 LocalTime 只能达到 23:59:59.999999999，所以不会立即起作用。

数学答案

你问的是什么：我的想法是计算与我定义的标准情况相比，夜间时间比白天时间多多少或少多少间隔开始和结束在 00:00。对于此计算，我们可以安全地取结束时间的余数模 24，因为它为我们提供了一天中正确的时间（夏令时转换和此类异常情况除外）。因此，将 e 设置为 e % 24 并定义一个函数 nMinusD，它给出了与 e == 0 相比，夜间比白天多多少小时，签名：

nMinusD(e) = e       for e <= 7
             14 - e  for 7 <= e <= 19
             e - 24  for e >= 19

在一张纸上画出曲线可能有助于理解。

对于开始时间，我们只需要将结果的符号反转即可。所以最终夜间和白天时间的有符号差是

diff = nMinusD(e) - nMinusD(s)

现在你可以看看diff的符号了。

diff > 0 => more nighttime hours than daytime hours
diff = 0 => equally many nighttime and daytime hours
diff < 0 => more daytime than nighttime hours

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

How to compute total overlap between multiple intervals nicely and efficiently?

algorithm

math

time

overlap

intervals

数学答案