โปรแกรมหาช่วงเวลา (Interval) ขนาดเล็กที่สุดครอบคลุม Query แต่ละตัวใน Python

ปัญหา

กำหนดรายการ Intervals แต่ละอันคือคู่ (left_i, right_i) และรายการ Queries สำหรับแต่ละ Query j ต้องหา Interval ขนาดเล็กที่สุดที่ครอบคลุม Query นั้น (left_i ≤ query ≤ right_i) คืนขนาด Interval (right_i - left_i + 1) ห้าไม่มีให้ -1

ตัวอย่าง

Intervals: [[2,5],[3,5],[4,7],[5,5]] Queries: [3,4,5,6]

Output: [3, 3, 1, 4]

อัลกอริทึม (Sort + Heap)

1. เรียง Intervals ใหญ่ไปเล็ก (Reverse)
2. เรียง Queries เล็กไปใหญ่
3. ใช้ Min-Heap เก็บ Intervals ที่ครอบคลุม Query ปัจจุบัน (Key = ขนาด Interval)
4. สำหรับแต่ละ Query: เพิ่ม Intervals ที่ left ≤ query ลง Heap, ลบ Intervals ที่ right < query ออก
5. Top ของ Heap = Interval ขนาดเล็กที่สุดที่ครอบคลุม Query นั้น

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

import heapq

def solve(intervals, queries):
    intervals = sorted(intervals)[::-1]  # เรียงใหญ่ไปเล็ก
    h = []  # Min-heap: (size, right)
    res = {}
    
    for q in sorted(queries):
        # เพิ่ม intervals ที่ left <= q
        while intervals and intervals[-1][0] <= q:
            i, j = intervals.pop()
            if j >= q:
                heapq.heappush(h, [j - i + 1, j])
        
        # ลบ intervals ที่ right < q
        while h and h[0][1] < q:
            heapq.heappop(h)
        
        res[q] = h[0][0] if h else -1
    
    return [res[q] for q in queries]

intervals = [[2,5],[3,5],[4,7],[5,5]]
queries = [3,4,5,6]
print(solve(intervals, queries))  # [3, 3, 1, 4]

ความซับซ้อน

• Time: O((n + q) log n)
• Space: O(n)