CSES - Reservations

You are given a list containing reservations as day ranges. Each range is a pair (a,b)(a,b), where 1ab1 \le a \le b: the reservation starts on the day aa and ends on the day bb.

Your task is to determine if the list contains two overlapping reservations, i.e., two ranges with one or more common days.

For example, the list [(4,7),(1,2)][(4,7),(1,2)] means that the first reservation is from the day 44 to the day 77, and the second reservation is from the day 11 to the day 22. These two reservations do not ovelap. On the other hand, the reservations on the list [(4,7),(1,5)][(4,7),(1,5)] do overlap, because both ranges contain the days 44 and 55.

In a file reservations.py, implement the function check_overlapping that takes a list of reservations as a parameter and returns True if any two ranges overlap, and False otherwise.

You should implement the function so that it runs efficiently even for long lists. The function should finish immediately in the last two test cases of the code template too.

import random

def check_overlapping(reservations):
    # TODO

if __name__ == "__main__":
    print(check_overlapping([])) # False
    print(check_overlapping([(1, 3)])) # False
    print(check_overlapping([(4, 7), (1, 2)])) # False
    print(check_overlapping([(4, 7), (1, 5)])) # True
    print(check_overlapping([(1, 1), (2, 2)])) # False
    print(check_overlapping([(1, 1), (1, 1)])) # True
    print(check_overlapping([(2, 3), (5, 5), (3, 4)])) # True
    print(check_overlapping([(2, 3), (5, 5), (1, 4)])) # True
    print(check_overlapping([(2, 3), (5, 5), (1, 5)])) # True

    reservations = [(day, day) for day in range(1, 10**5+1)]
    random.shuffle(reservations)
    print(check_overlapping(reservations)) # False

    reservations.append((42, 1337))
    random.shuffle(reservations)
    print(check_overlapping(reservations)) # True