Finding overlap intervals in a set of intervals-CodePudding

We have a login system that tracks how long people are connected. I would like to write a code to find people who were online at the same time. Look at this example, please:

P1: [1,7]
P2: [2,5]
P3: [3,4]
P4: [6,8]

Think of these as intervals of Person 1 to 4. I want the output of the algorithm to be something like this:

P1, P2 : [2, 3]
P1, P2, P3 : [3, 4]
P1, P2 : [4, 5]
P1, P4 : [6,7]

I tried to solve the problem with two for loops so that we get a list of people whose intervals overlap, but the problem is dealing with intervals for more than one person. for example, in the above example, [3,4] not have to come in [4, 5] in line three because it calculated as a three-person interval.

CodePudding user response：

Encode all interval bounds in a form like 1: P1, 7:-P1. Then sort all bounds chronologically and scan by increasing time. Also keep updated a list of the persons present by "excuting" insert or delete operations.

{} 1: P1 {P1} 2: P2 {P1, P2} 3: P3 {P1, P2, P3} 4:-P3 {P1, P2} 5:-P2 {P1} ...

Every configuration occurs between one time bound and the next.

Some configurations can repeat over time, but you did not specify how to handle them. With the above method, they will be listed separately.

CodePudding user response：

One approach, assuming the input is a dictionary of person -> interval:

from collections import defaultdict
from itertools import pairwise

data = {"P1": (1, 7),
        "P2": (2, 5),
        "P3": (3, 4),
        "P4": (6, 8)}

table = defaultdict(list)
for key, (start, end) in data.items():
    for i, j in pairwise(range(start, end   1)):
        table[(i, j)].append(key)

result = {k: v for k, v in table.items() if len(v) > 1}

for key, value in result.items():
    print(value, key)

Output

['P1', 'P2'] (2, 3)
['P1', 'P2', 'P3'] (3, 4)
['P1', 'P2'] (4, 5)
['P1', 'P4'] (6, 7)