หาช่วงที่ทับซ้อนกันใน Python

สมมติว่าเรามีรายการช่วง โดยแต่ละช่วงเป็นแบบ [start, end] แทนเวลาเริ่มต้นและสิ้นสุดของช่วง (รวม) เราต้องหาการทับซ้อนของพวกมัน คือช่วงที่อยู่ภายในช่วงที่กำหนดทั้งหมด

ตัวอย่าง

หากอินพุตคือ [[10, 110], [20, 60], [25, 75]] ผลลัพธ์จะเป็น [25, 60]

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

1. start, end := ช่วงหลังจากลบองค์ประกอบสุดท้ายออกจากรายการ intervals
2. ในขณะที่ intervals ไม่ว่าง:
   • start_temp, end_temp := ช่วงหลังจากลบองค์ประกอบสุดท้ายออกจากรายการ intervals
   • start := ค่าสูงสุดของ start, start_temp
   • end := ค่าต่ำสุดของ end, end_temp
3. คืนค่าช่วง [start, end]

การใช้งาน

class Solution:
    def solve(self, intervals):
        start, end = intervals.pop()
        while intervals:
            start_temp, end_temp = intervals.pop()
            start = max(start, start_temp)
            end = min(end, end_temp)
        return [start, end]

ob = Solution()
intervals = [[10, 110], [20, 60], [25, 75]]
print(ob.solve(intervals))

อินพุต

[[10, 110], [20, 60], [25, 75]]

เอาต์พุต

[25, 60]