CODEWITHSUNDEEP
pythondatetime
David
David

Reputation: 43

How to find gaps given a number of 'start' and 'end' datetime objects?

I have pairs of DateTime objects. Each DateTime object is either a 'start' or an 'end' of a time range. The time ranges overlap sometimes. I need to find the gaps.

I tried the DateTimeRange module off pypi, testing for intersecting ranges and then constructing encompassed ranges (as per their documentation) but I wasn't able to build these components into a piece of code that does what I want

EDIT: A 'gap' in this case is defined as any period of time between the earliest 'start' and the latest 'end' that is not encompassed by one of the pairs of 'start' and 'end' DateTime objects

import dateparser
from pprint import pprint

foo = []

foo.append({
    "start": dateparser.parse("8:00 AM"),
    "end": dateparser.parse("8:06 AM")
})

foo.append({
    "start": dateparser.parse("8:03 AM"),
    "end": dateparser.parse("8:07 AM")
})

foo.append({
    "start": dateparser.parse("8:02 AM"),
    "end": dateparser.parse("8:16 AM")
})

foo.append({
    "start": dateparser.parse("8:20 AM"),
    "end": dateparser.parse("8:30 AM")
})

pprint(foo)

#[{'end': datetime.datetime(2019, 2, 15, 8, 6),
#  'start': datetime.datetime(2019, 2, 15, 8, 0)},
# {'end': datetime.datetime(2019, 2, 15, 8, 7),
#  'start': datetime.datetime(2019, 2, 15, 8, 3)},
# {'end': datetime.datetime(2019, 2, 15, 8, 16),
#  'start': datetime.datetime(2019, 2, 15, 8, 2)},
# {'end': datetime.datetime(2019, 2, 15, 8, 30),
#  'start': datetime.datetime(2019, 2, 15, 8, 20)}]


find_gaps(foo)

#desired output
#
#[{'end': datetime.datetime(2019, 2, 15, 8, 20),
#  'start': datetime.datetime(2019, 2, 15, 8, 16)}]

Upvotes: 4

Views: 1989

Answers (1)

Endyd
Endyd

Reputation: 1279

You can sort your ranges based on the start times, then keep track of the end times until you find a gap between an end time and the next start time. If you find that gap, you append it. You need to advance the end time if the next end time is greater than the current end time. 

def find_gaps(ranges):
    if len(ranges) <= 1:
        return []

    # sort by start times
    ranges = sorted(ranges, key=lambda x:x['start'])

    gaps = []

    # Start at the end of the first range
    now = ranges[0]['end']

    # Iterate through ranges, ignoring the first range
    for pair in ranges[1:]:
        # if next start time is before current end time, keep going until we find a gap
        # if next start time is after current end time, found the first gap
        if pair['start'] > now:
            gaps.append({
                'start':now,
                'end':pair['start']
                })
        # need to advance "now" only if the next end time is past the current end time
        now = max(pair['end'], now)
    return gaps

Output: 

[{'end': datetime.datetime(2019, 2, 15, 8, 20),
  'start': datetime.datetime(2019, 2, 15, 8, 16)}]

Upvotes: 9

Related Questions