Tôi cần cấu trúc dữ liệu có thể lưu trữ các phạm vi không trùng lặp trong một thứ nguyên duy nhất. Toàn bộ phạm vi của kích thước không cần phải được bao phủ hoàn toàn.Cấu trúc dữ liệu cho các phạm vi không trùng lặp trong một kích thước duy nhất
Ví dụ sẽ là bộ lập lịch biểu phòng hội nghị. Kích thước là thời gian. Không có hai lịch biểu có thể trùng lặp. Phòng hội nghị không phải lúc nào cũng được lên lịch. Nói cách khác, trong một thời gian nhất định, có thể có tối đa một lịch biểu.
Giải pháp nhanh là phạm vi lưu trữ thời gian bắt đầu và kết thúc.
Range {
Date start
Date end
}
Điều này không được chuẩn hóa và yêu cầu thùng chứa thực thi không chồng chéo. Đối với hai phạm vi liền kề, kết thúc trước đó sẽ bị dư thừa với lần bắt đầu tiếp theo.
Một sơ đồ khác có thể bao gồm việc lưu trữ một giá trị biên với mỗi phạm vi. Nhưng đối với một chuỗi các dải ô liền nhau, sẽ luôn có thêm một giá trị ranh giới hơn các dải ô. Để làm được việc này các chuỗi có thể được biểu diễn dưới dạng xen kẽ các giá trị ranh giới và phạm vi:
B = ranh giới giá trị, r = phạm vi
BrBrB
Cấu trúc dữ liệu có thể trông giống như:
Boundary {
Date value
Range prev
Range next
}
Range {
Boundary start
Boundary end
}
Bản chất đó là danh sách được liên kết kép với các loại xen kẽ.
Cuối cùng, bất kỳ cấu trúc dữ liệu nào tôi sử dụng sẽ được thể hiện trong cả bộ nhớ (mã ứng dụng) và cơ sở dữ liệu quan hệ.
Tôi tò mò về những giải pháp học tập hoặc ngành đã cố gắng tồn tại.