How to the get the intersections of multiple periods

Question

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

I would consider establishing date ranges using the datetime module in Python, then looping through those lists of sequential dates and identifying any matches. Then proceed to create a new list of dates based on the most recent and least recent dates that exist without gaps. — rahlf23, Nov 06 '17 at 16:42
You might find the information available from [How to detect whether two date ranges overlap](https://stackoverflow.com/questions/325933/determine-whether-two-date-ranges-overlap/328558#328558) useful. Although the question is couched in terms of date/time ranges, any range type can be tested similarly. In context, you probably need to calculate the intersections of two of the sets of ranges, and then take that result and calculate the intersection of that with the third range. An easy optimization is to note that if the result range is empty, you can stop as the result will be empty too. — Jonathan Leffler, Nov 06 '17 at 17:02

score 3 · Accepted Answer · answered Nov 06 '17 at 17:02

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)

score 1 · Answer 2 · edited Jun 28 '23 at 17:50

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 []

score 0 · Answer 3 · answered Nov 06 '17 at 16:52

0

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]

answered Nov 06 '17 at 16:52

Acccumulation

3,491
1
8
12

I only want the periods where periods on all timelines intersect. What I understand from your psudo code could be accomplished with `set.intersection([set(r) for ranges in timelines for r in ranges])` – demux Nov 06 '17 at 17:01
@demux That might work if you insert `*`: `set.intersection(*[set(r) for ranges in timelines for r in ranges])` – Acccumulation Nov 06 '17 at 17:17
Not for what I'm doing, but it would be valid python. – demux Nov 06 '17 at 17:33

How to the get the intersections of multiple periods

3 Answers3