Finding all common ranges finding between multiple clients

Question

I am relatively new to coding. I encountered a problem that I can't find a solution for.

I have multiple "clients" , and each client has a few valid ranges (noted with the start and end point - e.g. (5,10) where 5 is the start point and 10 is the end point). I need to find a code that finds the common ranges across all of the clients (and if such range doesn't exist, then find the common range between all of the clients but 1, and so on..)

I have considered the naive approach of just calculating all of the possible permutations, but I couldn't get it to work (besides being computationally inefficient).

Important notes - The number of clients and ranges per client is not pre-determined, but can be calculated in run-time.

Simple example - Suppose I have 7 clients, as follows:

Client 1 - ranges are (17,30), (34,44)
Client 2 - ranges are (17,30), (31,44)
Client 3 - ranges are (25,30), (34,44)
Client 4 - ranges are (18,30), (34,44)
Client 5 - range is (19,44)
Client 6 - ranges are (20, 37), (38,44)
Client 7 - range is (20, 37)

The code should output (given this configuration) the following ranges - (25,30) and (34, 37)

I hope I described the problem properly, I'd be happy to clarify if necessary.

Thanks in advance!!

Welcome to Stack Overflow. How are you collecting the ranges, are they in a text file, already in a dict/iist in your code? What have you tried so far? — jwjhdev, Jan 20 '21 at 15:41
Hey - thanks for replying! @jwjhdev - The ranges are already formatted as a tuple-list form - each range is represented as a tuple, while every clients holds its own agents in a list. — Niv Yehezkel, Jan 20 '21 at 18:48
Does this answer your question? [Find the maximally intersecting subset of ranges](https://stackoverflow.com/questions/15013800/find-the-maximally-intersecting-subset-of-ranges) — Dave, Jan 20 '21 at 23:49
@Dave I don't think so, because in my case each "client" has its own LIST of ranges (and needs to consider just one of the ranges, per client) - rather than just intersecting all of the given ranges. Unless I misunderstand something? In any case, thanks for this! — Niv Yehezkel, Jan 21 '21 at 07:09

Paddy3118 · Accepted Answer · 2021-01-21T18:19:00.560

This method creates a "number line" of points starting and stopping individual ranges, then traverses the number line from minimum point upwards counting an occupancy of +1 for every range started, -1 for every range stopped.

The Code

"""

See: https://stackoverflow.com/questions/65812746/finding-all-common-ranges-finding-between-multiple-clients

Created on Wed Jan 20 17:28:44 2021

@author: Paddy3118
"""
from collections import defaultdict


clients = [[(17,30), (34,44)],
           [(17,30), (31,44)],
           [(25,30), (34,44)],
           [(18,30), (34,44)],
           [(19,44)],
           [(20, 37), (38,44)],
           [(20, 37)],
          ]

def ranges_singly(clients):
    "give each (lo, hi) range individually"
    return ([lo, hi] for c_ranges in clients for lo, hi in c_ranges)

def combine_ranges(c=clients):
    LO, HI = 'LO', 'HI'
    endpt = defaultdict(list)
    for lo, hi in ranges_singly(c):
        endpt[lo].append(LO)
        endpt[hi].append(HI)

    pt_order = sorted(endpt)
    last_pt, n  = None, 0
    sub_ranges = []
    for pt in pt_order:
        if n == 0:  # No clients in last_pt..pt
            pass
        else:
            sub_ranges.append((last_pt, pt, n))
        n += endpt[pt].count(LO)    # Ranges starting here
        n -= endpt[pt].count(HI)    # Ranges ending here
        last_pt = pt
    assert n == 0, f'Whoops n should end at zero not {n}'
    max_n = max(sub_ranges, key=lambda r:r[2])[-1]
    return max_n, [(lo, hi) for lo, hi, n in sub_ranges if n == max_n]

if __name__ ==  '__main__':
    print(combine_ranges(clients))      # (7, [(25, 30), (34, 37)])

Thanks Paddy! Much appreciated - the detailed code makes understanding it much simpler. I'll try to work over that - will comment again if I'll have any questions. — Niv Yehezkel, Jan 20 '21 at 19:53
@Paddy3118 - great approach. Would you mind elaborating a few key steps for easy understanding? — Daniel Hao, Jan 20 '21 at 21:46
Sure, but it's late for me, maybe if you have questions, I'll answer tomorrow. Cheers. — Paddy3118, Jan 20 '21 at 22:51
Hey @Paddy3118 I tried to follow, but I got lost. Is it based on a known algorithm? If so, mind giving me its name, so I can read further regarding this? Plus, I'd be really thankful if you're able to write a top level overview of the algorithm. Thanks again!! — Niv Yehezkel, Jan 21 '21 at 10:56
I have just followed Dave's link from the comments to your question and my solution is the same; only I extract all the individual ranges from your clients one-by-one using `ranges_singly` before applying the same essential algorithm. — Paddy3118, Jan 21 '21 at 13:56

Finding all common ranges finding between multiple clients

1 Answers1