1024. Video Stitching

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

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

Вам дана серия видеоклипов со спортивного соревнования, длительность которых составляет несколько секунд. Эти видеоклипы могут накладываться друг на друга и иметь различную длину. Каждый видеоклип описывается mảngом clips, где clips[i] = [starti, endi] указывает, что i-й клип начинается в starti и заканчивается в endi. Мы можем произвольно разрезать эти клипы на сегменты. НаVí dụ, клип [0, 7] может быть разрезан на сегменты [0, 1] + [1, 3] + [3, 7]. return минимальное количество клипов, необходимое для того, чтобы мы могли разрезать клипы на сегменты, охватывающие все спортивное событие [0, время]. Если Bài toán невыполнима, return -1.

Ví dụ:

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

Output: 3

C# lời giải

đã khớp/gố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++ lời giải

bản nháp tự động, xem lại trước khi gửi

#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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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 lời giải

đã khớp/gốc

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⃣Выбор клипов:

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

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

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

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

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.