Video Segment Score
MediumDynamic Programming · TikTok
You are building a highlight reel from candidate clips. Each entry of segments is [start, end, score], a clip covering the half-open time range [start, end) with length end - start.
Choose any set of clips such that:
- No two chosen clips overlap. Because ranges are half-open, a clip ending at time
tand another starting attdo not overlap. - The total length of the chosen clips is at most
max_duration.
Return the maximum total score of the chosen clips. Choosing nothing is allowed and scores 0.
Example 1
- Input:
- segments = [[0, 4, 10], [4, 7, 8], [2, 6, 15], [7, 9, 6]], max_duration = 7
- Output:
- 21
- Explanation
- Ignoring the budget,
[0,4),[4,7)and[7,9)fit together for 24, but their length is 9. Within 7, the best is[2,6)plus[7,9): length 4 + 2 = 6 and score 15 + 6 = 21.[0,4)with[4,7)also fits (length 7) but scores only 18.
Example 2
- Input:
- segments = [[0, 3, 5], [3, 6, 5], [1, 5, 9]], max_duration = 10
- Output:
- 10
- Explanation
[0,3)and[3,6)only touch at time 3, so both can be chosen for 10, which beats the single overlapping clip worth 9.
Example 3
- Input:
- segments = [[0, 10, 50], [20, 25, 4]], max_duration = 8
- Output:
- 4
- Explanation
- The 50-point clip is 10 long and exceeds the budget of 8, so the best is the 5-long clip worth 4.
Constraints
0 <= segments.length <= 1000 <= start < end <= 10^61 <= score <= 10^40 <= max_duration <= 1000