The LeetCode page for this task can be found here
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution | |
| { | |
| public int VideoStitching(int[][] clips, int T) | |
| { | |
| var dictionary = CreateClipDictionary(clips); | |
| var periodStart = 0; | |
| var periodEnd = 0; | |
| var minClipsNeeded = 0; | |
| do | |
| { | |
| var periodEndCandidates = GetEndCandidates(dictionary, periodStart, periodEnd); | |
| if (!periodEndCandidates.Any()) | |
| return -1; | |
| periodStart = periodEnd + 1; | |
| periodEnd = periodEndCandidates.Max(); | |
| minClipsNeeded++; | |
| } while (periodEnd < T); | |
| return minClipsNeeded; | |
| } | |
| private int[] GetEndCandidates(Dictionary<int, int[]> dict, int start, int end) | |
| { | |
| var candidates = new List<int>(); | |
| for (var index = start; index <= end; index++) | |
| { | |
| if (dict.ContainsKey(index)) | |
| { | |
| candidates.AddRange(dict[index]); | |
| } | |
| } | |
| return candidates.ToArray(); | |
| } | |
| private Dictionary<int, int[]> CreateClipDictionary(int[][] clips) | |
| { | |
| var dictionary = new Dictionary<int, List<int>>(); | |
| foreach (var clip in clips) | |
| { | |
| var clipStart = clip[0]; | |
| var clipEnd = clip[1]; | |
| if (dictionary.ContainsKey(clipStart)) | |
| { | |
| dictionary[clipStart].Add(clipEnd); | |
| } | |
| else | |
| { | |
| dictionary[clipStart] = new List<int> { clipEnd }; | |
| } | |
| } | |
| return dictionary.ToDictionary(kvp => kvp.Key, kvp => kvp.Value.ToArray()); | |
| } | |
| } |
by