โปรแกรมหาช่วงที่ต้องเพิ่มน้อยที่สุดเพื่อรวมช่วงทั้งหมดเป็นหนึ่งช่วงใน Python

สมมติว่าเรามีลิสต์ 2 มิติ intervals แต่ละแถวคือ [start, end] (รวม) สำหรับช่วง [a, b] (a < b) ขนาดคือ (b - a) เราต้องเพิ่มช่วงหนึ่งช่วงเข้าไปในลิสต์ ที่ทำให้หลังรวมช่วงทั้งหมดได้ช่วงเดียวพอดี หาขนาดน้อยที่สุดของช่วงที่เพิ่ม

ตัวอย่าง: intervals = [[15, 20], [30, 50]] ผลลัพธ์คือ 10 เพราะเพิ่ม [20, 30] ได้ขนาด 10

ขั้นตอนการแก้ปัญหา (Sweep Line)

1. สร้างลิสต์ events ว่าง
2. สำหรับแต่ละ (s, e) ใน intervals:
   • เพิ่ม (s, 1) เข้า events
   • เพิ่ม (e, -1) เข้า events
3. เรียงลำดับ events
4. curr_status = 0, last = None, interval = [0, 0]
5. สำหรับแต่ละ (time, status) ใน events:
   • ถ้า curr_status == 0 และ last มีค่า และ time > last:
     • ถ้า interval[0] == 0: interval[0] = last
     • interval[1] = time
   • last = time
   • curr_status += status
6. คืนค่า interval[1] - interval[0]

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

class Solution:
    def solve(self, intervals):
        events = []
        for s, e in intervals:
            events.append((s, 1))
            events.append((e, -1))
        events.sort()
        curr_status = 0
        last = None
        interval = [0, 0]
        for time, status in events:
            if curr_status == 0 and last and time > last:
                if interval[0] == 0:
                    interval[0] = last
                interval[1] = time
            last = time
            curr_status += status
        return interval[1] - interval[0]

ob = Solution()
intervals = [[15, 20], [30, 50]]
print(ob.solve(intervals))  # Output: 10

อินพุต / เอาต์พุต

Input: [[15, 20], [30, 50]]

Output: 10