CODEWITHSUNDEEP
pythonalgorithm
demux
demux

Reputation: 4654

How to the get the intersections of multiple periods

Psudo code:

timelines = [
    (range(<from>, <to>), range(<from>, <to>)),
    (range(<from>, <to>), range(<from>, <to>)),
    (range(<from>, <to>), range(<from>, <to>)),
]

<from> and <to> represent datetime objects

This "picture" shows after "Intersection" the values I need to calculate:

        |----------|    |----------|
               |------------|   |-------|
        |---------|     |------------|

Intersection   |--|     |---|   |--|

How do I calculate these intersections?

I'm coding in python, but answers in any programming language are welcome, as I only need to understand the algorithm

Upvotes: 2

Views: 2144

Answers (3)

demux
demux

Reputation: 4654

Here is my implementation of Felk's answer:

from functools import reduce
from psycopg2.extras import DateTimeTZRange


def _DateTimeTZRange_intersect(range1, range2):
    new_range = DateTimeTZRange(
        max(range1.lower, range2.lower),
        min(range1.upper, range2.upper)
    )
    return new_range if new_range.lower < new_range.upper else None

def DateTimeTZRange_intersect(*args):
    return reduce(_DateTimeTZRange_intersect, args) if args else []


def _DateTimeTZRange_intersect_2d(ranges1, ranges2):
    for range1 in ranges1:
        for range2 in ranges2:
            intersection = DateTimeTZRange_intersect(range1, range2)
            if intersection:
                yield intersection

def DateTimeTZRange_intersect_2d(*args):
    return reduce(_DateTimeTZRange_intersect_2d, args) if args else []

Upvotes: 1

Felk
Felk

Reputation: 8224

Step 0: Make a Range class for convenience:

from collections import namedtuple
Range = namedtuple("Range", ["start", "end"])

Step 1: Make a function that calculates the intersection between two ranges. This function will work for anything that consists of two comparable points:

def intersect(range1, range2):
    new_range = Range(
        max(range1.start, range2.start),
        min(range1.end, range2.end)
    )
    return new_range if new_range.start < new_range.end else None

Step 2: Make a function that finds all intersections of two sets of ranges, by just trying all possible combinations.

def intersect_two(ranges1, ranges2):
    for range1 in ranges1:
        for range2 in ranges2:
            intersection = intersect(range1, range2)
            if intersection:
                yield intersection

Step 3: reduce() a list of sets of ranges using intersect_two:

def intersect_all(ranges):
    return reduce(intersect_two, ranges)

I'm using integers for simplicity, but it should work just as good with datetime objects:

>>> timelines = [
...     (Range(0, 11), Range(15, 20)),
...     (Range(8, 16), Range(19, 25)),
...     (Range(0, 10), Range(15, 22)),
... ]
>>>
>>> for intersection in intersect_all(timelines):
...     print(intersection)
...
Range(start=8, end=10)
Range(start=15, end=16)
Range(start=19, end=20)

Upvotes: 3

Acccumulation
Acccumulation

Reputation: 3591

I'm coding in python, but answers in any programming language are welcome, as I only need to understand the algorithm

If you just want the pseudocode, one algorithm would be:

intersections = total_range
for timeline in timelines:
    intersections = intersection(timeline,intersections)

For implementing intersections, there are a few different methods. One is to use set function, although you have to convert to sets, and then if you don't want a set as output you have to convert back: intersections = intersections.intersection(timeline). Another method is list comprehension: intersections = [time_point for time_point in intersections if time_point in timeline]

Upvotes: 0

Related Questions