โปรแกรมรวมช่วงเวลา (Intervals) โดยเพิ่ม Target Interval ใน Python

ได้รับลิสต์ intervals ที่ ไม่ทับซ้อนและเรียงตาม end time และ target interval ใหม่ ต้อง insert และ merge ให้ intervals ยังคงไม่ทับซ้อนและเรียงลำดับ

ตัวอย่าง

intervals = [[1,15], [25,35], [75,90]], target = [10,30]

Output: [[1,35], [75,90]] (merge [1,15] กับ [25,35] ผ่าน target)

แนวทางแก้ปัญหา

1. เพิ่ม target เข้าไปในลิสต์
2. เรียงตาม start time
3. Merge แบบมาตรฐาน: เก็บ interval แรก → ถ้าตัวถัดไป start ≤ end ล่าสุด → merge (update end = max) มิฉะนั้น append ใหม่

การใช้งาน (Python)

class Solution:
    def solve(self, intervals, target):
        intervals.append(target)
        intervals.sort(key=lambda x: x[0])
        
        merged = [intervals[0]]
        for interval in intervals[1:]:
            if interval[0] <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], interval[1])
            else:
                merged.append(interval)
        
        return merged

# ทดสอบ
ob = Solution()
intervals = [[1,15], [25,35], [75,90]]
target = [10, 30]
print(ob.solve(intervals, target))  # Output: [[1, 35], [75, 90]]

ความซับซ้อน

• Time Complexity: O(N log N) (จากการ sort)
• Space Complexity: O(N)

ถ้า intervals เรียงอยู่แล้ว สามารถทำได้ O(N) โดยไม่ต้อง sort