Проверка интервалов Python

Не могли бы мне подсказать как возможно оптимизировать данную задачу? На большом кол-ве данных программа требует большого кол-ва времени.

Вход:

1. Первая строка входных данных содержит количество наборов тестовых данных. Затем следуют t наборов.

2. Первая строка набора содержит n отрезков времени. В следующих n строках следуют описания отрезков.

Условия:

1. часы, минуты и секунды заданы корректно (то есть часы находятся в промежутке от 0 до 2, а минуты и секунды — в промежутке от 0 до 59);
2. левая граница отрезка находится не позже его правой границы (но границы могут быть равны);
3. никакая пара отрезков не пересекается (даже в граничных моментах времени).

Необходимо проверить входящие интервалы на данные условия. В случае, если все условия выполняются, то вывести 'YES', иначе вывести 'NO'.

Я написал следующий код:

import datetime
import sys


def get_datetime_from_string(str_date):
    try:
        return datetime.datetime.strptime(str_date.rstrip(), '%H:%M:%S')
    except ValueError:
        return None


class Range:
    def __init__(self, start, end):
        self.start_datetime = start
        self.end_datetime = end

    def __repr__(self):
        return f" ({self.start_datetime} - {self.end_datetime})"


def is_intersection(dates, date_range):
    for date in dates:
        if date_range.start_datetime == date.start_datetime or date_range.end_datetime == date.end_datetime \
                or date_range.start_datetime == date.end_datetime or date_range.end_datetime == date.start_datetime:
            return True
        if date_range.start_datetime < date.end_datetime and date.start_datetime < date_range.end_datetime:
            return True
    return False


def main():
    t = int(sys.stdin.readline())
    for i in range(t):
        dates = []
        lines = int(sys.stdin.readline())
        is_no = False
        for line in range(lines):
            if is_no:
                _ = sys.stdin.readline()
                continue
            dt_1, dt_2 = map(get_datetime_from_string, sys.stdin.readline().split('-'))
            if not dt_1 or not dt_2:
                is_no = True
                continue
            if dt_1 > dt_2:
                is_no = True
                continue
            date_range = Range(dt_1, dt_2)
            if is_intersection(dates, date_range):
                is_no = True
                continue
            dates.append(date_range)
        else:
            print('YES') if not is_no else print('NO')


if __name__ == '__main__':
    main()

На вход в консоли поступает:

5
1
22:13:56-22:13:55
1
00:00:00-23:59:59
1
23:59:59-00:00:00
2
00:00:00-23:59:59
00:00:00-23:59:59
2
13:44:59-13:44:59
13:45:00-13:45:00

Ответ:

NO
YES
NO
NO
YES

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

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