Giả sử chúng ta có một tập hợp các khoảng thời gian gồm các cặp 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ụ là kiểm tra xem có khoảng thời gian nào trong tập hợp này chồng chéo hoàn toàn lên khoảng thời gian khác hay không. Nếu có chồng chéo, trả về True, ngược lại trả về False.
Ví dụ, nếu đầu vào là [(4,6), (10,12), (7,9), (13,16)], thì đầu ra sẽ là False. Nếu đầu vào là [(4,6), (4,9), (7,11), (5,8)], thì đầu ra sẽ là True.
Các bước giải quyết:
- Sắp xếp danh sách các khoảng thời gian.
- Duyệt từ i = 1 đến kích thước danh sách:
- Nếu intervals[i][1] <= intervals[i-1][1] (thời gian kết thúc của khoảng hiện tại nhỏ hơn hoặc bằng khoảng trước), trả về True.
- Trả về False.
Xem ví dụ dưới đây để 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