Как проверить, есть ли перекрытие между временными окнами

Question

Вам предоставляется список пар. Каждая пара хранит даты начала и окончания, представляющие временное окно. Задача состоит в том, чтобы проверить, есть ли какое-либо перекрытие.

Обратите внимание, что проблему можно решить тривиально, используя два вложенных цикла for для цикла periods и несколько условий для проверки отсутствия перекрытий. Однако мне интересно посмотреть, есть ли более удобочитаемое и элегантное решение, которое поддерживает циклы и если операторы минимальны и которое не обязательно использует стандартную библиотеку.

Перекрытия не обязательно возникают между смежными записями.

Ожидается, что в списке periods будет менее 10 временных окон. Я не беспокоюсь о времени процессора. Я обеспокоен читаемостью кода.

from datetime import datetime

overlapping_periods = [
    [datetime(2019, 1, 1), datetime(2019, 1, 5)],
    [datetime(2019, 1, 6), datetime(2019, 1, 10)],
    [datetime(2019, 1, 9), datetime(2019, 1, 15)],
]
non_overlapping_periods = [
    [datetime(2019, 1, 1), datetime(2019, 1, 5)],
    [datetime(2019, 1, 6), datetime(2019, 1, 10)],
    [datetime(2019, 1, 11), datetime(2019, 1, 15)],
]

# Find an elegant `verify_overlaps`.
verify_overlaps(overlapping_periods)  # True
verify_overlaps(non_overlapping_periods)  # False

Answer 1

вы можете использовать функцию sorted, которая возвращает итерацию (по умолчанию она будет сортироваться по первому аргументу в вашем списке):

def verify_overlap(periods):
    d2_previous = datetime(1900,1,1)
    for d1, d2 in (sorted(periods)):
        if d1 <= d2_previous:
            return False
        d2_previous = d2
    return True

Answer 2

Не знаю, считаете ли вы это более читабельным, но:

import itertools
from typing import NamedTuple


class Period(NamedTuple):
    start: datetime
    end: datetime

    def __and__(self, other):
        return (
            other.start in self or
            self.start in other
        )

    def __contains__(self, dt):
        return dt >= self.start and dt < self.end


def pairwise(iterable):
    a, b = itertools.tee(iterable)
    next(b, None)
    return zip(a, b)


def verify_overlaps(periods):
    return any(a & b for a, b in pairwise(sorted(periods)))

Answer 3

Может ли это быть так просто, или я что-то упустил?

def verify_overlaps(s):
    s = sorted(s) # sorts on first member of each element by default
    current = datetime.min
    for dt0, dt1 in s:
        if dt0 <= current:
            return False
        current = dt1
    return True

Вы не указали, если начало одного периода, совпадающее с концом другого периода, считается перекрытием. Это просто вопрос "<" против "<=". </p>