โปรแกรมหาช่วงเวลายาวสุดจากการรวม intervals ทับซ้อนใน Python

สมมติว่ามีรายการ intervals แบบ [start, end] ต้องการหาช่วงเวลายาวสุดที่ได้จากการรวม intervals ที่ทับซ้อนกัน

ตัวอย่าง: [[1,6],[4,9],[5,6],[11,14],[16,20]] ผลลัพธ์ 9 รวมได้ [1,9] ความยาว 9

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

1. เรียง intervals
2. union = intervals[0], best = union[1] - union[0] + 1
3. วน s, e ใน intervals[1:]:
   • ถ้า s <= union[1]: union[1] = max(union[1], e)
   • มิฉะนั้น: union = [s, e]
   • best = max(best, union[1] - union[0] + 1)
4. คืน best

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

class Solution:
    def solve(self, intervals):
        intervals.sort()
        union = intervals[0]
        best = union[1] - union[0] + 1
        for s, e in intervals[1:]:
            if s <= union[1]:
                union[1] = max(union[1], e)
            else:
                union = [s, e]
            best = max(best, union[1] - union[0] + 1)
        return best

ob = Solution()
intervals = [[1, 6], [4, 9], [5, 6], [11, 14], [16, 20]]
print(ob.solve(intervals))

อินพุต

[[1, 6], [4, 9], [5, 6], [11, 14], [16, 20]]

เอาต์พุต

9