โปรแกรมค้นหาระยะเวลาที่ไม่ซ้ำกันทั้งหมดจากรายการช่วงเวลาใน Python

สมมติว่าเรามีรายการของช่วงเวลาที่แต่ละรายการแทนช่วงเวลา [เริ่มต้น, สิ้นสุด] (รวม) เราต้องหาระยะเวลาที่ไม่ซ้ำกันทั้งหมดที่ครอบคลุม

ดังนั้น ถ้าอินพุตเหมือนช่วง =[[2, 11],[13, 31],[41, 61]] เอาต์พุตจะเป็น 50 เนื่องจากระยะทางที่ครอบคลุมทั้งหมดที่ไม่ซ้ำกันคือ (11 - 2 + 1) =10 จากนั้น (31 - 13 + 1) =19 และ (61 - 41 + 1) =21 ดังนั้นยอดรวมคือ 50

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

• ถ้ารายการช่วงเวลาว่างเปล่า ดังนั้น
  • คืน 0
• เรียงช่วงรายการ
• [เริ่ม สิ้นสุด] :=ช่วงเวลา[0]
• ตอบ :=0
• สำหรับการเริ่มต้นและสิ้นสุดแต่ละครั้ง (s, e) ในช่วงเวลา ให้ทำ
  • ถ้า s> จบ แล้ว
    • ans :=ans + end - start + 1
    • start :=s, end :=e
  • มิฉะนั้น
    • สิ้นสุด :=สูงสุดของจุดสิ้นสุด e
• ans :=ans + end - start + 1
• คืนสินค้า

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

class Solution:
   def solve(self, intervals):
      if not intervals:
         return 0
         intervals.sort()
         start, end = intervals[0]
         ans = 0
         for s, e in intervals:
            if s > end:
               ans += end - start + 1
               start = s
               end = e
            else:
               end = max(end, e)
            ans += end - start + 1
         return ans
ob = Solution()
intervals = [[2, 11],[13, 31],[41, 61]]
print(ob.solve(intervals))

อินพุต

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

ผลลัพธ์

50