ภาพรวม
บทความนี้แนะนำวิธีตรวจสอบว่ามีช่วงเวลา (interval) ใดช่วงหนึ่งที่ "ทับซ้อนกันสมบูรณ์" (completely overlap) กับอีกช่วงหนึ่งในชุดข้อมูลหรือไม่ โดยช่วงเวลาถูกแทนด้วยคู่ (start, end)
เงื่อนไขการทับซ้อนสมบูรณ์
ช่วงเวลา (a, b) ทับซ้อนสมบูรณ์กับ (c, d) ถ้า a <= c และ b >= d (หรือในทางกลับกัน) กล่าวคือ ช่วงหนึ่งครอบคลุมอีกช่วงหนึ่งทั้งหมด
อัลกอริทึม
- จัดเรียงลิสต์ช่วงเวลาตามค่าเริ่มต้น (start)
- เปรียบเทียบช่วงเวลาปัจจุบันกับช่วงก่อนหน้า: ถ้าค่าสิ้นสุด (end) ของช่วงปัจจุบัน <= ค่าสิ้นสุดของช่วงก่อนหน้า แสดงว่ามีการทับซ้อนสมบูรณ์
ตัวอย่างโค้ด Python
def solve(intervals):
intervals.sort()
for i in range(1, len(intervals)):
if intervals[i][1] <= intervals[i-1][1]:
return True
return False
intervals1 = [(4,6), (10,12), (7,9), (13,16)]
intervals2 = [(4,6), (4,9), (7,11), (5,8)]
print(solve(intervals1)) # False
print(solve(intervals2)) # True
ผลลัพธ์
False True
คำอธิบายเพิ่มเติม
การจัดเรียง (sort) ทำให้ช่วงเวลาที่เริ่มต้นก่อนอยู่หน้า หากช่วงต่อมาสิ้นสุดก่อนหรือเท่ากับช่วงก่อนหน้า แสดงว่าถูกครอบคลุมทั้งหมด สิ่งนี้มีประโยชน์ในการตรวจสอบการจองทรัพยากรหรือตารางเวลา
