How to check if a Datetime is within a list of dictionaries of datetime intervals

user_11361401 0
Viewed 65

I have a YAML file that contains a sequence of time intervals. I would like to load this YML into my Python script and then check if another datetime is within any of these intervals.

YML file:

ignore_state_change:
  - start_time_utc: 2021-08-04 23:25:00.31099+00:00
    end_time_utc: 2021-08-05 00:25:00.31099+00:00
  - start_time_utc: 2021-08-05 01:25:00.31099+00:00
    end_time_utc: 2021-08-05 02:25:00.31099+00:00

Loading script:

import yaml
with open(r'test.yml') as file:
    config = yaml.load(file, Loader=yaml.FullLoader)
for item in config['ignore_state_change']:
    print(item)

Result:

{'start_time_utc': datetime.datetime(2021, 8, 4, 23, 25, 0, 310990, tzinfo=datetime.timezone.utc), 'end_time_utc': datetime.datetime(2021, 8, 5, 0, 25, 0, 310990, tzinfo=datetime.timezone.utc)}
{'start_time_utc': datetime.datetime(2021, 8, 5, 1, 25, 0, 310990, tzinfo=datetime.timezone.utc), 'end_time_utc': datetime.datetime(2021, 8, 5, 2, 25, 0, 310990, tzinfo=datetime.timezone.utc)}

Now I would like to check if a datetime variable event_time_utc is within any of the start/end time intervals above. Obvious solution to iterate through each dictionary item and do if statement with >start_time_utc and <end_time_utc does not seem to be time efficient or elegant. What would be the best way to do such task?

Thanks!

yaml algorithm python
1 Answers

Here's an O((n log n) + (m log n)) solution (where n is the count of StartTime-EndTime pairs and m is the count of dates event_time_utc to search) that would work whether there are overlapping dates in the yaml file or none.

  1. O(n) Get all the StartTime-EndTime pairs 
    [['2021-01-15' - '2021-01-25'], ['2021-03-01' - '2021-03-02'], ['2021-01-01' - '2021-01-20']]
  2. O(n log n) Sort the StartTime-EndTime pairs in a way that the earliest ones are at the start of the list and the latest ones at the end of the list. 
    [['2021-01-01' - '2021-01-20'], ['2021-01-15' - '2021-01-25'], ['2021-03-01' - '2021-03-02']]
  3. O(n) Merge each consecutive StartTime-EndTime pair in the sorted list if they would cover the same time. 
    [['2021-01-01' - '2021-01-25'], ['2021-03-01' - '2021-03-02']]
  4. O(m log n) Now, all we need to do for every date event_time_utc is to perform a binary search on the sorted-merged list. Since it is already sorted and merged, we could now just check if the date is in range of the StartTime-EndTime pair in the insertion point in the sorted list.

test.yml

ignore_state_change:
  - start_time_utc: 2021-08-04 23:25:00.31099+00:00
    end_time_utc: 2021-08-05 00:25:00.31099+00:00
  - start_time_utc: 2021-10-01 00:00:00.00000+00:00
    end_time_utc: 2021-10-02 23:59:59.99999+00:00
  - start_time_utc: 2021-08-17 23:23:23.00000+00:00
    end_time_utc: 2021-09-30 23:59:59.99999+00:00
  - start_time_utc: 2021-08-09 22:22:22.00000+00:00
    end_time_utc: 2021-08-17 23:23:23.00000+00:00
  - start_time_utc: 2021-08-05 01:25:00.31099+00:00
    end_time_utc: 2021-08-05 02:25:00.31099+00:00
  - start_time_utc: 2020-05-25 00:00:00.00000+00:00
    end_time_utc: 2020-06-25 00:00:00.00000+00:00
  - start_time_utc: 2021-08-11 00:00:00.00000+00:00
    end_time_utc: 2021-08-13 23:59:59.99999+00:00
  - start_time_utc: 2021-08-11 00:00:00.00000+00:00
    end_time_utc: 2021-08-13 23:59:59.99999+00:00
  - start_time_utc: 2020-06-15 00:00:00.00000+00:00
    end_time_utc: 2020-07-25 00:00:00.00000+00:00

script.py

import bisect
from datetime import datetime, timezone
import yaml

# Get the timestamps
with open(r'test.yml') as file:
    config = yaml.load(file, Loader=yaml.FullLoader)
print("Config file")
for i, a in enumerate(config['ignore_state_change']):
    print(i, a)
print()

# Sort the timestamps
dt_sorted = []
for item in config['ignore_state_change']:
    bisect.insort(dt_sorted, [item["start_time_utc"], item["end_time_utc"]])
print("Sorted timestamps")
for i, a in enumerate(dt_sorted):
    print(i, a)
print()

# Merge the timestamps
dt_merged = [dt_sorted[0]]
for dt in dt_sorted[1:]:
    if dt[0] <= dt_merged[-1][1]:
        dt_merged[-1][1] = max(dt_merged[-1][1], dt[1])
    else:
        dt_merged.append(dt)
print("Merged timestamps")
for i, a in enumerate(dt_merged):
    print(i, a)
print()

# Binary search each time in the merged timestamps
print("Results")
for event_time_utc in [
    datetime(2021, 10, 1, 0, 0, tzinfo=timezone.utc),
    datetime(2021, 8, 17, 23, 23, 23, tzinfo=timezone.utc),
    datetime(2021, 8, 5, 0, 25, 0, 310991, tzinfo=timezone.utc),
    datetime(2021, 8, 5, 0, 25, 0, 310990, tzinfo=timezone.utc),
    datetime(2021, 8, 5, 0, 26, 0, 310990, tzinfo=timezone.utc),
    datetime(2021, 8, 5, 1, 26, 0, 310990, tzinfo=timezone.utc),
    datetime(2021, 8, 5, 1, 25, 0, 310990, tzinfo=timezone.utc),
    datetime(2020, 5, 24, 0, 0, tzinfo=timezone.utc),
    datetime(2020, 5, 25, 0, 0, tzinfo=timezone.utc),
    datetime(2020, 6, 25, 1, 0, tzinfo=timezone.utc),
    datetime(2020, 6, 25, 0, 0, tzinfo=timezone.utc),
    datetime(1993, 1, 2, 3, 4, tzinfo=timezone.utc),
    datetime(2021, 10, 2, 23, 59, 59, 999990, tzinfo=timezone.utc),
    datetime(2021, 11, 2, 23, 59, 59, 999990, tzinfo=timezone.utc),
    datetime(2021, 8, 14, 1, 26, 0, 310990, tzinfo=timezone.utc),
]:
    ref_point = bisect.bisect_left(dt_merged, [event_time_utc, event_time_utc])
    for index in (ref_point - 1, ref_point):
        if (
            0 <= index < len(dt_merged)
            and dt_merged[index][0] <= event_time_utc <= dt_merged[index][1]
        ):
            print(f"{event_time_utc} is in range of {dt_merged[index]}")
            break
    else:
        print(f"{event_time_utc} is not in range")

Output

Config file
0 {'start_time_utc': datetime.datetime(2021, 8, 4, 23, 25, 0, 310990, tzinfo=datetime.timezone.utc), 'end_time_utc': datetime.datetime(2021, 8, 5, 0, 25, 0, 310990, tzinfo=datetime.timezone.utc)}
1 {'start_time_utc': datetime.datetime(2021, 10, 1, 0, 0, tzinfo=datetime.timezone.utc), 'end_time_utc': datetime.datetime(2021, 10, 2, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)}
2 {'start_time_utc': datetime.datetime(2021, 8, 17, 23, 23, 23, tzinfo=datetime.timezone.utc), 'end_time_utc': datetime.datetime(2021, 9, 30, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)}
3 {'start_time_utc': datetime.datetime(2021, 8, 9, 22, 22, 22, tzinfo=datetime.timezone.utc), 'end_time_utc': datetime.datetime(2021, 8, 17, 23, 23, 23, tzinfo=datetime.timezone.utc)}
4 {'start_time_utc': datetime.datetime(2021, 8, 5, 1, 25, 0, 310990, tzinfo=datetime.timezone.utc), 'end_time_utc': datetime.datetime(2021, 8, 5, 2, 25, 0, 310990, tzinfo=datetime.timezone.utc)}
5 {'start_time_utc': datetime.datetime(2020, 5, 25, 0, 0, tzinfo=datetime.timezone.utc), 'end_time_utc': datetime.datetime(2020, 6, 25, 0, 0, tzinfo=datetime.timezone.utc)}
6 {'start_time_utc': datetime.datetime(2021, 8, 11, 0, 0, tzinfo=datetime.timezone.utc), 'end_time_utc': datetime.datetime(2021, 8, 13, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)}
7 {'start_time_utc': datetime.datetime(2021, 8, 11, 0, 0, tzinfo=datetime.timezone.utc), 'end_time_utc': datetime.datetime(2021, 8, 13, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)}
8 {'start_time_utc': datetime.datetime(2020, 6, 15, 0, 0, tzinfo=datetime.timezone.utc), 'end_time_utc': datetime.datetime(2020, 7, 25, 0, 0, tzinfo=datetime.timezone.utc)}

Sorted timestamps
0 [datetime.datetime(2020, 5, 25, 0, 0, tzinfo=datetime.timezone.utc), datetime.datetime(2020, 6, 25, 0, 0, tzinfo=datetime.timezone.utc)]
1 [datetime.datetime(2020, 6, 15, 0, 0, tzinfo=datetime.timezone.utc), datetime.datetime(2020, 7, 25, 0, 0, tzinfo=datetime.timezone.utc)]
2 [datetime.datetime(2021, 8, 4, 23, 25, 0, 310990, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 8, 5, 0, 25, 0, 310990, tzinfo=datetime.timezone.utc)]
3 [datetime.datetime(2021, 8, 5, 1, 25, 0, 310990, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 8, 5, 2, 25, 0, 310990, tzinfo=datetime.timezone.utc)]
4 [datetime.datetime(2021, 8, 9, 22, 22, 22, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 8, 17, 23, 23, 23, tzinfo=datetime.timezone.utc)]
5 [datetime.datetime(2021, 8, 11, 0, 0, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 8, 13, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)]
6 [datetime.datetime(2021, 8, 11, 0, 0, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 8, 13, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)]
7 [datetime.datetime(2021, 8, 17, 23, 23, 23, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 9, 30, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)]
8 [datetime.datetime(2021, 10, 1, 0, 0, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 10, 2, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)]

Merged timestamps
0 [datetime.datetime(2020, 5, 25, 0, 0, tzinfo=datetime.timezone.utc), datetime.datetime(2020, 7, 25, 0, 0, tzinfo=datetime.timezone.utc)]
1 [datetime.datetime(2021, 8, 4, 23, 25, 0, 310990, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 8, 5, 0, 25, 0, 310990, tzinfo=datetime.timezone.utc)]
2 [datetime.datetime(2021, 8, 5, 1, 25, 0, 310990, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 8, 5, 2, 25, 0, 310990, tzinfo=datetime.timezone.utc)]
3 [datetime.datetime(2021, 8, 9, 22, 22, 22, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 9, 30, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)]
4 [datetime.datetime(2021, 10, 1, 0, 0, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 10, 2, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)]

Results
2021-10-01 00:00:00+00:00 is in range of [datetime.datetime(2021, 10, 1, 0, 0, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 10, 2, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)]
2021-08-17 23:23:23+00:00 is in range of [datetime.datetime(2021, 8, 9, 22, 22, 22, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 9, 30, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)]
2021-08-05 00:25:00.310991+00:00 is not in range
2021-08-05 00:25:00.310990+00:00 is in range of [datetime.datetime(2021, 8, 4, 23, 25, 0, 310990, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 8, 5, 0, 25, 0, 310990, tzinfo=datetime.timezone.utc)]
2021-08-05 00:26:00.310990+00:00 is not in range
2021-08-05 01:26:00.310990+00:00 is in range of [datetime.datetime(2021, 8, 5, 1, 25, 0, 310990, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 8, 5, 2, 25, 0, 310990, tzinfo=datetime.timezone.utc)]
2021-08-05 01:25:00.310990+00:00 is in range of [datetime.datetime(2021, 8, 5, 1, 25, 0, 310990, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 8, 5, 2, 25, 0, 310990, tzinfo=datetime.timezone.utc)]
2020-05-24 00:00:00+00:00 is not in range
2020-05-25 00:00:00+00:00 is in range of [datetime.datetime(2020, 5, 25, 0, 0, tzinfo=datetime.timezone.utc), datetime.datetime(2020, 7, 25, 0, 0, tzinfo=datetime.timezone.utc)]
2020-06-25 01:00:00+00:00 is in range of [datetime.datetime(2020, 5, 25, 0, 0, tzinfo=datetime.timezone.utc), datetime.datetime(2020, 7, 25, 0, 0, tzinfo=datetime.timezone.utc)]
2020-06-25 00:00:00+00:00 is in range of [datetime.datetime(2020, 5, 25, 0, 0, tzinfo=datetime.timezone.utc), datetime.datetime(2020, 7, 25, 0, 0, tzinfo=datetime.timezone.utc)]
1993-01-02 03:04:00+00:00 is not in range
2021-10-02 23:59:59.999990+00:00 is in range of [datetime.datetime(2021, 10, 1, 0, 0, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 10, 2, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)]
2021-11-02 23:59:59.999990+00:00 is not in range
2021-08-14 01:26:00.310990+00:00 is in range of [datetime.datetime(2021, 8, 9, 22, 22, 22, tzinfo=datetime.timezone.utc), datetime.datetime(2021, 9, 30, 23, 59, 59, 999990, tzinfo=datetime.timezone.utc)]
user_110438250
Related