Problem Overview

Given multiple video segments from a sports event lasting T seconds, each segment is represented as [start, end]. These segments may overlap and have varying lengths. We can freely split and recombine segments—for instance, [0, 7] can be divided into [0, 1] + [1, 3] + [3, 7].

The objective is to recombine these segments to create a continuous piece that covers [0, T]. Return the minimum number of segments required, or -1 if this is impossible.

Examples

clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10 → 3

Select [0,2], [8,10], [1,9], then split [1,9] into [1,2] + [2,8] + [8,9]. Result: [0,2] + [2,8] + [8,10] covers the full range [0, 10].

clips = [[0,1],[1,2]], T = 5 → -1

The segments [0,1] and [1,2] only cover up to time 2, leaving the interval [2, 5] uncovered.

clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], T = 9 → 3

Optimal choice: [0,4], [4,7], [6,9].

clips = [[0,4],[2,8]], T = 5 → 2

Clips may extend beyond the event duration, which is acecptable.

Constraints

• 1 <= clips.length <= 100
• 0 <= clips[i][0], clips[i][1] <= 100
• 0 <= T <= 100

Solution: Greedy Approach

Algorithm

1. Sort clips by start time, breaking ties by end time (descending)
2. Use a greedy strategy to build the minimum number of segmenst
3. Always select the clip that extends farthest while maintaining connectivity

Implementation

/**
 * @param {number[][]} segments
 * @param {number} totalTime
 * @return {number}
 */
function combineVideoSegments(segments, totalTime) {
  if (totalTime === 0) return 0;
  
  // Sort by start time, then by end time descending
  segments.sort((a, b) => {
    if (a[0] === b[0]) return b[1] - a[1];
    return a[0] - b[0];
  });

  const selected = [];
  
  // Check if coverage starts at 0
  if (segments[0][0] > 0) return -1;

  let currentEnd = 0;
  let nextEnd = 0;
  let index = 0;

  while (currentEnd < totalTime) {
    // Find the clip that extends farthest within current reach
    while (index < segments.length && segments[index][0] <= currentEnd) {
      nextEnd = Math.max(nextEnd, segments[index][1]);
      index++;
    }

    // No valid segment found
    if (nextEnd === currentEnd) return -1;

    selected.push([currentEnd, nextEnd]);
    currentEnd = nextEnd;
  }

  return selected.length;
}

Alternative: Map-Based Approach

/**
 * @param {number[][]} clips
 * @param {number} target
 * @return {number}
 */
function stitchVideos(clips, target) {
  if (target === 0) return 0;
  
  // Group clips by their start time
  const byStart = new Map();
  for (const clip of clips) {
    const start = clip[0];
    const end = clip[1];
    if (!byStart.has(start)) {
      byStart.set(start, []);
    }
    byStart.get(start).push({ start, end });
  }

  // Sort each group by end time descending
  for (const group of byStart.values()) {
    group.sort((a, b) => b.end - a.end);
  }

  // Must have a clip starting at 0
  const initial = byStart.get(0);
  if (!initial || initial.length === 0) return -1;

  let current = initial[0];
  let segments = 1;

  // Greedily extend coverage
  while (current.end < target) {
    const candidates = [];
    const upperBound = current.end;

    // Look for clips starting within current segment that extend further
    for (let t = upperBound - 1; t >= current.start; t--) {
      const group = byStart.get(t);
      if (group && group[0].end > current.end) {
        candidates.push(group[0]);
      }
    }

    if (candidates.length === 0) return -1;
    
    // Pick the one extending farthest
    candidates.sort((a, b) => b.end - a.end);
    current = candidates[0];
    segments++;
  }

  return segments;
}

Complexity Analysis

• Time Complexity: O(n log n) due to sorting
• Space Complexity: O(n) for the sorted array and auxiliary structures

Key Insight

The greedy strategy works because at each step, choosing the clip that extends farthest while maintaining connectivity ensures we never miss an optimal solution. This is a classic interval covering problem solvable with a greedy approach.