UniLecs #Task. Алгоритм склеек при видеомонтаже
Задача: алгоритм программы для видеомонтажа. Дан список видеонарезок фильма, некоторые из них содержат одни и те же видеофрагменты, например, 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)]
Разбор
Линейный перебор списка, т.к. при худшем случае, все видеоотрезки не будут иметь наложений.
В цикле перебираем все видеофрагменты. Сравниваем текущий временной отрезок с последним в результирующем списке, если у них есть общий хронометраж, то объединяем их в один и обновляем результирующий список. В противном случае, помещаем текущий отрезок как отдельный фрагмент в результирующий список. Так перебор возможен, т.к. исходный список отсортирован по минуте начале видеофрагмента.
Детали реализации смотрите ниже.
Реализация
https://gist.github.com/unilecs/8c217375b132fd3b47b3f8ba648aeb4f
