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

สมมติว่ามีรายการ intervals แบบ [start, end] (inclusive) ต้องการหาเวลาทั้งหมดที่ครอบคลุม (union duration)

ตัวอย่าง: intervals = [[2,11],[13,31],[41,61]] ผลลัพธ์ 50: (11-2+1)=10, (31-13+1)=19, (61-41+1)=21

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

1. ถ้าว่าง คืน 0
2. เรียง intervals
3. start, end = intervals[0], ans = 0
4. วน s, e ใน intervals:
   • ถ้า s > end: ans += end - start + 1, start=s, end=e
   • มิฉะนั้น: end = max(end, e)
5. ans += end - start + 1
6. คืน ans

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

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