โปรแกรมหาช่วงที่ไม่ตัดช่วงตัดใน Python

สมมติว่าเรามีรายการช่วงที่เรียงลำดับและไม่ปะติดปะต่อกัน และรายการอื่นที่ตัดทอน ซึ่งแสดงถึงช่วงเวลา เราต้องลบทุกส่วนของช่วงที่ตัดกับช่วงการตัดออก แล้วคืนรายการใหม่

ดังนั้น ถ้าอินพุตเหมือนช่วง =[[2, 11],[13, 31],[41, 61]] cut =[8, 46] ผลลัพธ์จะเป็น [[2, 8], [46 , 61]]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• cut_start, cut_end :=ตัด
• ans :=รายการใหม่
• สำหรับการเริ่มต้นแต่ละครั้ง สิ้นสุดในช่วงเวลา ทำ
  • ถ้าสูงสุด cut_start และ start <ขั้นต่ำ end และ cut_end แล้ว
    • ถ้าเริ่ม
    • ใส่ช่วง [start, cut_start] ลงใน ans
  • ถ้าจบ> cut_end แล้ว
    • ใส่ช่วง [cut_end, end] ลงใน 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]]