You are given a list containing reservations as day ranges. Each range is a pair , where : the reservation starts on the day and ends on the day .
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 means that the first reservation is from the day to the day , and the second reservation is from the day to the day . These two reservations do not ovelap. On the other hand, the reservations on the list do overlap, because both ranges contain the days and .
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