Video Stitching ใน C++

คำอธิบายปัญหา

มีคลิปวิดีโอหลายคลิปจากงานแข่งขันที่ใช้เวลา T วินาที แต่ละคลิป clips[i] = [start, end] สามารถตัดคลิปได้อย่างอิสระ ต้องการหาจำนวนคลิปน้อยที่สุดที่สามารถต่อกันได้เพื่อครอบคลุม [0, T] หากไม่ได้ ให้คืน -1

ตัวอย่าง: clips=[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T=10 → 3 (ใช้ [0,2], [1,9], [8,10])

วิธีแก้ปัญหา (Greedy + Interval Coverage)

1. สร้างอาร์เรย์ v ขนาด T+1 เก็บจุดสิ้นสุดสูงสุดที่เริ่มจากเวลาแต่ละจุด
2. v[start] = max(v[start], min(end, T))
3. ใช้ greedy: เริ่มจาก curr = v[0], หาก v[0] == -1 คืน -1
4. วนหาช่วงถัดไปที่เริ่ม <= curr และสิ้นสุดไกลที่สุด (next)
5. อัปเดต curr = next, เพิ่มจำนวนคลิป
6. ทำซ้ำจน curr >= T หรือไม่พบช่วงต่อไป

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int T) {
        vector<int> v(T + 1, -1);
        int n = clips.size();
        
        for(int i = 0; i < n; i++) {
            if(clips[i][0] > T) continue;
            v[clips[i][0]] = max(v[clips[i][0]], min(clips[i][1], T));
        }
        
        if(v[0] == -1) return -1;
        int curr = v[0];
        int ret = 1;
        int i = 1;
        int next = 0;
        
        while(curr < T && i <= n) {
            while(i <= curr && i <= T) {
                next = max(next, v[i]);
                i++;
            }
            if(next == curr || next == -1) return -1;
            curr = next;
            ret++;
        }
        return curr >= T ? ret : -1;
    }
};

int main() {
    vector<vector<int>> v1 = {{0,2},{4,6},{8,10},{1,9},{1,5},{5,9}};
    Solution ob;
    cout << ob.videoStitching(v1, 10);
    return 0;
}

อินพุต

[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]] 10

เอาต์พุต

3