Determining overlapping intervals

Question

I have two machines, and for each machine I have the intervals during which it was working as a list of the start points and list of the end points of the intervals (for example [0, 5, 9] and [3, 6, 13] would indicate that the machine was working from time 0 to 3, 5 to 6, and 9 to 13).

I would like to determine how to calculate the start and end points of intervals where exactly one machine was working and exactly two machines were working are the same time.

For instance if the start and end points of the second machine intervals were [0, 7] and [2, 10] then the start and end points of intervals where exactly one machine was working are [2, 5, 7, 10] and [3, 6, 9, 13] and the start and end points of intervals where exactly two machines were working are [0, 9] and [2, 10].

I would like to be able to generalize this to three or more machines as well.

This is what I have:

overlapping_interval_starts = {}
overlapping_interval_ends = {}
whole_list = [(start, 's') for start in interval_starts] + [(end, 'e') for end in interval_ends]
whole_list.sort()

count = 1
if whole_list:
    previous, _ = whole_list.pop(0)
    for elt, elt_type in whole_list:
        current = elt
        if (count != 0) and (previous != current):
            try:
                overlapping_interval_starts[count].append(previous)
                overlapping_interval_ends[count].append(current)
            except KeyError:
                overlapping_interval_starts[count] = [previous]
                overlapping_interval_ends[count] = [current]

        if elt_type == 's':
            count += 1
        else:
            count -= 1
        previous = current

It works on the example problem I have, but I am not sure how to verify it is correct in general.

For instance running it on the following problem:

Machine 1: [2, 7], [6, 11]
Machine 2: [1, 5, 11], [3, 10, 13]
Machine 3: [2, 6], [5, 8]

yields:

overlapping_interval_starts = {1: [1, 10, 11],
                               2: [3, 5, 6, 8],
                               3: [2, 7]}
overlapping_interval_ends = {1: [2, 11, 13],
                             2: [5, 6, 7, 10],
                             3: [3, 8]}

which is technically correct, but there should really only be two intervals (3 to 7 and 8 to 10) where two machines overlap. So I am struggling to see how I can be sure it works in general.

Determining overlapping intervals

Answers (1)

Related Questions