算法 - 在循环世界（24小时）中寻找重叠时间段的持续时间

Question

我一直在尝试找出两个时间范围之间重叠小时数的算法，例如：

应该返回12。

和

应该返回4。

因此，请帮助我填写以下函数的空缺：

public static Long findOverlappingInterval(Long startTime1, Long endTime1,
                                           Long startTime2, Long endTime2){ 
    // Any suggestions?
}

谢谢。

编辑： 我知道创建两个二进制数组的解决方案，使用AND并总结结果。 意思是：

但这并不能满足我的具体需求，因为我想在Solr查询中使用该算法的思想，所以对我来说使用数组和二进制运算符不是一个选项。

- Daniel

---

在第二个例子中，这个"broken interval"（破碎的时间段）是指什么？你会如何用startTime和endTime来表示它？ - Rahul Jain

@RahulJain startTime = 12，endTime = 2。这是一个循环世界。 - Daniel

我一直在尝试为你发布代码，但是StackOverflow不断警告我缩进不正确。 - Rahul Jain

Answer 1

_{令人惊讶的是，在短时间内有很多答案...}

我遵循了其他答案中已经提出的相同思路：当起始时间s小于结束时间e时，结果可以分解为两个单独的计算，分别针对范围[s,24]和[0,e]。

这可以“互相”完成，因此只需要考虑3种简单情况，其余情况可以使用递归调用来完成。

然而，我尝试着

• 考虑到（根据图片），端点应该是包含的！
• 添加更多的测试用例
• 美观地可视化配置 :-)

这是一个MCVE的结果：

public class OverlappingIntervals
{
    private static final long INTERVAL_SIZE = 24;

    public static void main(String[] args)
    {
        test(6,23, 2,17);
        test(0,12, 12,2);

        test(11,4, 12,3);
        test(12,4, 11,3);
    }

    private static void test(
        long s0, long e0, long s1, long e1)
    {
        System.out.println(createString(s0, e0, s1, e1));
        System.out.println(findOverlappingInterval(s0, e0, s1, e1));
    }

    private static String createString(
        long s0, long e0, long s1, long e1)
    {
        StringBuilder sb = new StringBuilder();
        sb.append(createString(s0, e0, "A")).append("\n");
        sb.append(createString(s1, e1, "B"));
        return sb.toString();
    }

    private static String createString(long s, long e, String c)
    {
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<INTERVAL_SIZE; i++)
        {
            if (s < e)
            {
                if (i >= s && i <= e)
                {
                    sb.append(c);
                }
                else
                {
                    sb.append(".");
                }
            }
            else 
            {
                if (i <= e || i >= s)
                {
                    sb.append(c);
                }
                else 
                {
                    sb.append(".");
                }
            }
        }
        return sb.toString();
    }



    public static long findOverlappingInterval(
        long s0, long e0, long s1, long e1)
    {
        return compute(s0, e0+1, s1, e1+1);
    }

    public static long compute(
        long s0, long e0, long s1, long e1)
    {
        if (s0 > e0)
        {
            return 
                compute(s0, INTERVAL_SIZE, s1, e1) +
                compute(0, e0, s1, e1);
        }
        if (s1 > e1)
        {
            return 
                compute(s0, e0, s1, INTERVAL_SIZE) +
                compute(s0, e0, 0, e1);
        }
        return Math.max(0, Math.min(e0, e1) - Math.max(s0, s1));
    }
}

前两个测试案例是问题中给出的，在适当位置打印出 12 和 4。剩下的两个测试案例是用于测试其他重叠配置的。

......AAAAAAAAAAAAAAAAAA
..BBBBBBBBBBBBBBBB......
12
AAAAAAAAAAAAA...........
BBB.........BBBBBBBBBBBB
4
AAAAA......AAAAAAAAAAAAA
BBBB........BBBBBBBBBBBB
16
AAAAA.......AAAAAAAAAAAA
BBBB.......BBBBBBBBBBBBB
16

然而，需要注意的是，为了覆盖所有可能情况，可能需要创建更多的测试配置。

- Marco13

Answer 2

您可以不创建数组，只需计算区间之间的交集。有三种情况：

1. 没有分裂的区间。
2. 一个区间被分裂。
3. 两个区间都被分裂。

您可以将分裂的区间问题视为两个单独的区间来解决。使用递归，您可以轻松地完成此操作：

public static Long findOverlappingInterval(Long startTime1, Long endTime1, Long startTime2, Long endTime2)
{
    if (startTime1 < endTime1 && startTime2 < endTime2) 
        return Math.max(0, Math.min(endTime2, endTime1) - Math.max(startTime1, startTime2) + 1);
    else
    {
        if (startTime1 < endTime1) 
            return findOverlappingInterval(startTime1, endTime1, 0L, endTime2) + 
                   findOverlappingInterval(startTime1, endTime1, startTime2, 23L);
        else if (startTime2 < endTime2) 
            return findOverlappingInterval(0L, endTime1, startTime2, endTime2) + 
                   findOverlappingInterval(startTime1, 23L, startTime2, endTime2);
        else
        {
            return findOverlappingInterval(0L, endTime1, 0L, endTime2) +
                   findOverlappingInterval(0L, endTime1, startTime2, 23L) +
                   findOverlappingInterval(startTime1, 23L, 0L, endTime2) +
                   findOverlappingInterval(startTime1, 23L, startTime2, 23L);
        }
    }
}

- Arturo Menchaca

---

我认为不必明确处理两个间隔都被分割的情况：当第一个情况通过递归调用进行处理时，它永远不会（必须）到达最终的“else”情况。尽管如此，对于清晰的描述和（有效且高效的）解决方案，我还是要点赞。 - Marco13

Answer 3

首先，对于区间(a, b)，其中(a > b)，我们可以轻松地将其分为两个区间。

(a , 23) and (0, b)

因此，问题变成找到 (a, b) 和 (a1, b1) 之间的重叠部分，其中 a <= b 且 a1 <= b1。

所以，有四种情况：

• b < a1 或 b1 < a，这意味着没有重叠，返回0
• a <= a1 && b1 <= b，这意味着 (a, b) 包含 (a1, b1)，返回 b1 - a1 + 1
• a1 <= a && b <= b1，这意味着 (a1, b1) 包含 (a, b)，返回 b - a + 1
• 最后一种情况是 (a, b) 和 (a1, b1) 的重叠部分，该重叠区间为 (max(a1, a), min(b, b1))

- Pham Trung

Answer 4

/** Start times must be smaller than end times */
public static int findOverlappingInterval(int startTime1, int endTime1, int startTime2, int endTime2) {
    int overlappingTime = 0;
    int[] time1 = new int[Math.abs(endTime1 - startTime1)];
    for (int i1 = startTime1; i1 < endTime1; i1++) {
        time1[i1 - startTime1] = i1;
    }
    int[] time2 = new int[Math.abs(endTime2 - startTime2)];
    for (int i2 = startTime2; i2 < endTime2; i2++) {
        time2[i2 - startTime2] = i2;
    }

    for (int i = 0; i < time1.length; i++) {
        for (int j = 0; j < time2.length; j++) {
            if (time1[i] == time2[j]) {
                overlappingTime++;
            }
        }
    }
    return overlappingTime;
}

这个方法应该可以实现你想要的功能。对我来说它有效。但是我不确定包装部分是否正确。

编辑

/** Returns the overlap between the four time variables */
public static int findOverlappingInterval(int startTime1, int endTime1, int startTime2, int endTime2) {
    int overlappingTime = 0;

    // First time
    int time1Length = 0;
    if (endTime1 < startTime1) {
        time1Length = 24 - startTime1;
        time1Length += endTime1;
    }
    int[] time1;
    if (time1Length == 0) {
        time1 = new int[Math.abs(endTime1 - startTime1)];
        for (int i1 = startTime1; i1 < endTime1; i1++) {
            time1[i1 - startTime1] = i1;
        }
    } else {
        time1 = new int[time1Length];
        int count = 0;
        for (int i1 = 0; i1 < endTime1; i1++) {
            time1[count] = i1;
            count++;
        }
        for (int i1 = startTime1; i1 < 24; i1++) {
            time1[count] = i1;
            count++;
        }
    }

    // Second time
    int time2Length = 0;
    if (endTime2 < startTime2) {
        time2Length = 24 - startTime2;
        time2Length += endTime2;
    }
    int[] time2;
    if (time2Length == 0) {
        time2 = new int[Math.abs(endTime2 - startTime2)];
        for (int i2 = startTime2; i2 < endTime2; i2++) {
            time2[i2 - startTime2] = i2;
        }
    } else {
        time2 = new int[time2Length];
        int count = 0;
        for (int i2 = 0; i2 < endTime2; i2++) {
            time2[count] = i2;
            count++;
        }
        for (int i2 = startTime2; i2 < 24; i2++) {
            time2[count] = i2;
            count++;
        }
    }

    // Overlap calculator
    for (int i = 0; i < time1.length; i++) {
        for (int j = 0; j < time2.length; j++) {
            if (time1[i] == time2[j]) {
                overlappingTime++;
            }
        }
    }
    return overlappingTime;
}

这段新代码应该可以满足你的需求。它会在24小时内循环运行。

- James Burnell

---

我无法做出“开始时间必须小于结束时间”的假设。在第二个例子中，“startTime”大于“endTime”。 - Daniel

我现在已经添加了一个循环。 - James Burnell

看起来效率不高，应该存在一种不那么朴素的解决方案。 - AdamSkywalker

我同意。虽然这就是我想出来的。xD。它有效。这才是最重要的。除非它实际上会引起问题。此外，有时简单的任务需要复杂的解决方案。 - James Burnell

Answer 5

请查看此链接：Ideone 链接

_{编辑：在此处插入链接中的代码：}

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
    public static Long min(Long a,Long b){
        return ((a)<(b)?(a):(b));
    }
    public static Long max(Long a,Long b){
        return ((a)>(b)?(a):(b));
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        Long s1=6L,e1=23L,s2=2L,e2=17L,ans=0L;
        Boolean broken1,broken2;
        broken1=(s1<=e1)?false:true;
        broken2=(s2<=e2)?false:true;
        if(broken1){
            if(broken2)
                ans=min(e1,e2)+1 + 23-max(s1,s2)+1;
            else{
                if(e1>=s2) ans+=(min(e1,e2)-s2+1);
                if(s1<=e2) ans+=(e2-max(s1,s2)+1);
            }
        }
        else{
            if(broken2){
                if(e2>=s1) ans+=(min(e1,e2)-s1+1);
                if(s2<=e1) ans+=(e1-max(s1,s2)+1);
            }
            else{
                if(e1<s2 || e2<s1) ans=0L;
                else ans=min(e1,e2)-max(s1,s2)+1;
            }
        }
        System.out.println(ans+"");
    }
}

- Rahul Jain