Algorithms - Find duration of overlapping intervals in a cyclic world (24 hours)

Question

I've been trying to figure out the algorithm for finding the number of overlapping hours between two time ranges, for example:

Should return 12.

And

Should return 4.

So please help me fill in the gaps in creating the following function:

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

Thanks.

EDIT: I'm aware of the solution of creating two binary arrays, using AND and summing up the result. Meaning:

But that would not help my specific needs since i want to use the idea of the algorithm for a solr query, so using arrays and binary operators is not an option for me.

Answer 1

_{Surprisingly many answers in a short time...}

I followed the same idea that was already proposed in other answers: When start time s is smaller than the end time e, then the result can be broken down into two separate computations, for the ranges [s,24] and [0,e].

This can be done "mutually" so there are only 3 simple cases to consider, and the remaining ones can be done with recursive calls.

However, I tried to

• consider the fact that (according to the images), the end points should be inclusive (!)
• Add some more test cases
• Visualize the configurations nicely :-)

This is the result as an 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));
    }
}

The first two test cases are the ones that have been given in the question, and they properly print 12 and 4, respectively. The remaining two are intended for testing other overlap configurations:

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

However, note that further test configurations may have to be created in order to cover all possible cases.

Answer 2

You can do it without creating an array, just calculating intersections between intervals. There are three cases:

1. No splitted intervals.
2. One splitted interval.
3. Both intervals are splitted.

You can solve the problem of splitted intervals as two separate intervals. Using recursion you can do this easily:

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);
        }
    }
}

Answer 3

First, for interval (a, b) which (a > b), we can easily break it into two intervals

(a , 23) and (0, b)

So, the problem become finding the overlapping between (a , b) and (a1, b1) with a <= b and a1 <= b1

So, there are four cases:

• b < a1 or b1 < a , which means there is no overlapping, return 0
• a <= a1 && b1 <= b, which means (a, b) contains (a1, b1), return b1 - a1 + 1
• a1 <= a && b <= b1, which means (a1, b1) contains (a, b), return b - a + 1
• Last case is (a, b) and (a1, b1) overlapped part of each interval, that overlapping interval is (max(a1, a), min(b, b1))