1024. Video Stitching

leetcode medium

#array#csharp#greedy#leetcode#math#medium#sort

Task

Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается массивом 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

C# solution

matched/original

public class Solution {
    public int VideoStitching(int[][] clips, int T) {
        Array.Sort(clips, (a, b) => a[0] == b[0] ? b[1].CompareTo(a[1]) : a[0].CompareTo(b[0]));
        int end = -1, end2 = 0, res = 0;
        
        foreach (var clip in clips) {
            if (end2 >= T || clip[0] > end2) break;
            if (end < clip[0] && clip[0] <= end2) {
                res++;
                end = end2;
            }
            end2 = Math.Max(end2, clip[1]);
        }
        return end2 >= T ? res : -1;
    }
}

C++ solution

auto-draft, review before submit

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int VideoStitching(int[][] clips, int T) {
        Array.Sort(clips, (a, b) => a[0] == b[0] ? b[1].CompareTo(a[1]) : a[0].CompareTo(b[0]));
        int end = -1, end2 = 0, res = 0;
        
        foreach (var clip in 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;
    }
}

Java solution

matched/original

import java.util.Arrays;

public class Solution {
    public int videoStitching(int[][] clips, int T) {
        Arrays.sort(clips, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int end = -1, end2 = 0, res = 0;
        
        for (int[] clip : clips) {
            if (end2 >= T || clip[0] > end2) break;
            if (end < clip[0] && clip[0] <= end2) {
                res++;
                end = end2;
            }
            end2 = Math.max(end2, clip[1]);
        }
        return end2 >= T ? res : -1;
    }
}

JavaScript solution

matched/original

class Solution {
    videoStitching(clips, T) {
        clips.sort((a, b) => a[0] - b[0] || b[1] - a[1]);
        let end = -1, end2 = 0, res = 0;
        
        for (const [start, finish] of clips) {
            if (end2 >= T || start > end2) break;
            if (end < start && start <= end2) {
                res++;
                end = end2;
            }
            end2 = Math.max(end2, finish);
        }
        return end2 >= T ? res : -1;
    }
}

Go solution

matched/original

import "sort"

func videoStitching(clips [][]int, T int) int {
    sort.Slice(clips, func(i, j int) bool {
        return clips[i][0] < clips[j][0] || (clips[i][0] == clips[j][0] && clips[i][1] > clips[j][1])
    })
    end, end2, res := -1, 0, 0
    for _, clip := range clips {
        if end2 >= T || clip[0] > end2 {
            break
        }
        if end < clip[0] && clip[0] <= end2 {
            res++
            end = end2
        }
        end2 = max(end2, clip[1])
    }
    if end2 >= T {
        return res
    }
    return -1
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

1⃣Сортировка клипов:

Отсортируйте клипы по начальным значениям. Если начальные значения равны, отсортируйте по конечным значениям в убывающем порядке.

2⃣Выбор клипов:

Используйте жадный алгоритм для выбора клипов. Начните с начальной точки 0 и двигайтесь вперед, выбирая клип, который может покрыть наибольший диапазон.

Если обнаруживается, что начальная точка текущего клипа больше текущей позиции, это означает, что клипы не могут покрыть промежуток, и нужно вернуть -1.

3⃣Проверка покрытия:

Продолжайте процесс, пока не покроете весь диапазон от 0 до T. Если в конце процесса достигнута или превышена точка T, верните количество использованных клипов, иначе верните -1.

😎