Giả sử, chúng ta được cung cấp một tập hợp các khoảng bao gồm các giá trị (a, b) trong đó a đại diện cho thời gian bắt đầu và b đại diện cho thời gian kết thúc của một sự kiện. Nhiệm vụ của chúng ta là kiểm tra xem bất kỳ khoảng nào trong số này hoàn toàn trùng lặp với bất kỳ khoảng nào khác trong tập hợp này hay không. Nếu bất kỳ khoảng thời gian nào trùng nhau, chúng tôi trả về kết quả là Đúng, nếu không, chúng tôi trả về Sai.
Vì vậy, nếu đầu vào là [(4,6), (10,12), (7,9), (13,16)], thì đầu ra sẽ là Sai. Nếu đầu vào là [(4,6), (4,9), (7,11), (5,8)], thì đầu ra sẽ là True.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- sắp xếp các khoảng thời gian trong danh sách
- đối với tôi trong phạm vi từ 1 đến kích thước khoảng thời gian, hãy thực hiện
- nếu khoảng [i, 1] <=khoảng [i- 1, 1], thì
- trả về True
- trả về Sai
- nếu khoảng [i, 1] <=khoảng [i- 1, 1], thì
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
def solve(intervals): intervals.sort() for i in range(1, len(intervals)): if intervals[i][1] <= intervals[i- 1][1]: return True return False intervals = [(4,6),(10,12),(7,9),(13,16)] intervals2 = [(4,6), (4,9), (7,11), (5,8)] print(solve(intervals)) print(solve(intervals2))
Đầu vào
[(4,6),(10,12),(7,9),(13,16)] [(4,6), (4,9), (7,11), (5,8)]
Đầu ra
False True