UniLecs #Task. Алгоритм склеек при видеомонтаже

Albert Davletov
Nov 4 · 2 min read

Задача: алгоритм программы для видеомонтажа. Дан список видеонарезок фильма, некоторые из них содержат одни и те же видеофрагменты, например, 1й фрагмент содержит хронометраж фильма с 10й по 15ю минуту, 2й фрагмент содержит хронометраж фильма с 13й по 17ю минуту. Необходимо получить список видеосклеек фильма, которые не содержат дублирующего хронометража. То есть для нашего примера, итоговой склейкой будет видеофайл с 10й по 17ю минуту.

Входные данные: (Start(i), End(i)) — массив видеонарезок, где start(i) — минута начала видеофрагмента, end(i) — минута конца видеофрагмента. Список отсортирован по минуте начала каждого видеофрагмента.

Вывод: (Start(i), End(i)) — массив видеосклеек фильма, которые не содержат дублирующего хронометража.

Пример:
1. Input: [(1,5), (3,7), (4,6), (6,8)]
Output: [(1,8)]

2. Input: [(1,5), (3,7), (4,6), (6,8), (10,12), (11,15)]
Output: [(1,8), (10, 15)]

Разбор

Линейный перебор списка, т.к. при худшем случае, все видеоотрезки не будут иметь наложений.
В цикле перебираем все видеофрагменты. Сравниваем текущий временной отрезок с последним в результирующем списке, если у них есть общий хронометраж, то объединяем их в один и обновляем результирующий список. В противном случае, помещаем текущий отрезок как отдельный фрагмент в результирующий список. Так перебор возможен, т.к. исходный список отсортирован по минуте начале видеофрагмента.
Детали реализации смотрите ниже.

Реализация

C#: Merge timelines
C#: Main() function

https://gist.github.com/unilecs/8c217375b132fd3b47b3f8ba648aeb4f

Play-test

https://dotnetfiddle.net/DwoHrH

Albert Davletov

Written by

UniLecs

UniLecs

Задачи по алгоритмизации и программированию, а также новости из мира IT.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade