1024. Video Stitching

LeetCode medium original: C# #array #csharp #greedy #leetcode #math #medium #sort

선택한 UI 언어에 맞게 문제 텍스트를 러시아어에서 번역합니다. 코드는 변경하지 않습니다.

LeetCode Static

Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается 배열ом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. На예제, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. return минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если 문제 невыполнима, return -1.

예제:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10

Output: 3

C# 해법

매칭됨/원본

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++ 해법

자동 초안, 제출 전 검토

#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 해법

매칭됨/원본

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 해법

매칭됨/원본

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 해법

매칭됨/원본

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
}

Algorithm

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

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

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

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

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

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

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

😎

Vacancies for this task

활성 채용 with overlapping task tags are 표시됨.

전체 채용

아직 활성 채용이 없습니다.