Cho một loạt các đoạn video từ sự kiện thể thao kéo dài T giây. Các đoạn có thể chồng chéo và độ dài khác nhau. Mỗi đoạn clips[i] là khoảng [clips[i][0], clips[i][1]]. Ta có thể cắt tự do các đoạn. Tìm số đoạn tối thiểu để cắt thành các segment bao phủ toàn bộ [0, T]. Nếu không thể, trả về -1.
Ví dụ: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10, kết quả = 3 (lấy [0,2], [8,10], [1,9]).
Giải pháp tham lam:
Tạo mảng v kích thước T+1, điền -1
Với mỗi clip: v[clip[0]] = max(v[clip[0]], min(clip[1], T))
curr = v[0], nếu -1 trả về -1
i = 1, ret = 1, next = 0
While curr < T và i ≤ n:
While i ≤ curr: next = max(next, v[i]), i++
Nếu next == curr hoặc next == -1: trả về -1
curr = next, ret++Trả về ret nếu curr ≥ T, ngược lại -1
Ví dụ
#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)); } int curr = v[0]; if(v[0] == -1)return -1; int i = 1; int ret = 1; int next = 0; while(curr < T && i <= n){ while(i <= curr){ 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)); }Đầu vào
[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]] 10
Đầu ra
3