โปรแกรมหา intervals ที่ไม่ทับกับ cut interval ใน Python

สมมติว่ามี intervals เรียงแล้วไม่ทับซ้อน และ cut interval ต้องการลบส่วนที่ทับกับ cut ออก คืน intervals ที่เหลือ

ตัวอย่าง: intervals = [[2,11],[13,31],[41,61]], cut = [8,46] ผลลัพธ์ [[2,8],[46,61]]

ขั้นตอนการแก้ปัญหา

1. cut_start, cut_end = cut, ans = []
2. วน start, end ใน intervals:
   • ถ้า max(cut_start, start) < min(end, cut_end) (มีการทับ):
     • ถ้า start < cut_start: เพิ่ม [start, cut_start]
     • ถ้า end > cut_end: เพิ่ม [cut_end, end]
   • มิฉะนั้น: เพิ่ม [start, end] ทั้งหมด
3. คืน ans

ตัวอย่างโค้ด

class Solution:
    def solve(self, intervals, cut):
        cut_start, cut_end = cut
        ans = []
        for start, end in intervals:
            if max(cut_start, start) < min(end, cut_end):
                if start < cut_start:
                    ans.append([start, cut_start])
                if end > cut_end:
                    ans.append([cut_end, end])
            else:
                ans.append([start, end])
        return ans

ob = Solution()
intervals = [[2, 11], [13, 31], [41, 61]]
cut = [8, 46]
print(ob.solve(intervals, cut))

อินพุต

[[2, 11], [13, 31], [41, 61]], [8, 46]

เอาต์พุต

[[2, 8], [46, 61]]