Сложность: medium
Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. Например, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. Верните минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если задача невыполнима, верните -1.
Пример:
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3
👨💻 Алгоритм:
1⃣Сортировка клипов:
Отсортируйте клипы по начальным значениям. Если начальные значения равны, отсортируйте по конечным значениям в убывающем порядке.
2⃣Выбор клипов:
Используйте жадный алгоритм для выбора клипов. Начните с начальной точки 0 и двигайтесь вперед, выбирая клип, который может покрыть наибольший диапазон.
Если обнаруживается, что начальная точка текущего клипа больше текущей позиции, это означает, что клипы не могут покрыть промежуток, и нужно вернуть -1.
3⃣Проверка покрытия:
Продолжайте процесс, пока не покроете весь диапазон от 0 до T. Если в конце процесса достигнута или превышена точка T, верните количество использованных клипов, иначе верните -1.
😎 Решение:
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {
sort(clips.begin(), clips.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
});
int end = -1, end2 = 0, res = 0;
for (const auto& clip : clips) {
if (end2 >= T || clip[0] > end2) break;
if (end < clip[0] && clip[0] <= end2) {
res++;
end = end2;
}
end2 = max(end2, clip[1]);
}
return end2 >= T ? res : -1;
}
};Ставь 👍 и забирай 📚 Базу знаний