# Dynamic Programming

• You are working on developing a movie with Amazon Video and want to devise an application to easily break up individual shots in a video into scenes. There is already an algorithm that breaks the video up into shots (short sequences from a particular camera angle) and lables them.

Write a function which will partition a sequence of labels into minimal subsequences so that no labels appear in more than one subsequence. The output should be the length of each subsequence.

Input:
The input to the function/method consists of an argument - inputList, a list of characters representing the sequence of shots.

Output:
Return a list of integers representing the length of each scene, in the order in which it appears in the given sequence of shots.

Example:

• Input:
inputList = [a,b,a,b,c,b,a,c,a,d,e,f,e,g,d,e,h,i,j,h,k,l,i,j]
• Output:
[9, 7, 8]

Explanation:
The correct partitioning is:
a,b,a,b,c,b,a,c,a,/d,e,f,e,g,d,e,/h,i,j,h,k,l,i,j
To ensure that no label appears in more than one subsequence, subsequencea are as small as possible, and subsequences partition the sequence. The length of these subsequences are 9, 7 and 8.

• package myAlgos;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.*;

// CLASS BEGINS, THIS CLASS IS REQUIRED
class Interval {
int start;
int end;
char value;

Interval(char value, int start){
this.value = value;
this.start = start;
this.end = start;
}

public String toString(){

return value +"["+start+":"+end+"]";
}

}

public class Solution {

public static void main(String[] args) {
Solution ml = new Solution();
System.out.println("Result");
System.out.println(ml.lengthEachScene(new ArrayList<Character>(Arrays.asList('a', 'b', 'c', 'e', 'a', 'e', 'f', 'g', 'h', 'i', 'j', 'e'))));
System.out.println("Result");
System.out.println(ml.lengthEachScene(new ArrayList<Character>(Arrays.asList('a','b','a','b','c','b','a','c','a','d','e','f','e','g','d','e','h','i','j','h','k','l','i','j'))));
System.out.println("Result");
System.out.println(ml.lengthEachScene(new ArrayList<Character>(Arrays.asList('a', 'b', 'c','a'))));
System.out.println("Result");
System.out.println(ml.lengthEachScene(new ArrayList<Character>(Arrays.asList('a', 'b', 'c', 'd', 'a', 'e', 'f', 'g', 'h', 'i', 'j', 'e'))));

}

List<Integer> lengthEachScene(List<Character> inputList){

List<Integer> result = new ArrayList<>();
Map<Character, Interval> occuranceMap = new LinkedHashMap<>();

List<Interval> l = new ArrayList<>();
for(int i = 0; i < inputList.size(); i++){
char cur = inputList.get(i);
if(occuranceMap.containsKey(cur)){
occuranceMap.get(cur).end = i;
}
else{
occuranceMap.put(cur, new Interval(cur, i));
}
}

List<Interval> listP = new ArrayList<Interval>(occuranceMap.values());

System.out.println(listP);
Interval prev = listP.get(0);

for(int i = 1; i < listP.size(); i++){

Interval cur = listP.get(i);
if( prev.end < cur.start ){

prev.start = cur.start;
prev.end = cur.end;
}
else{
if(prev.end > cur.end){
continue;
}
else{
prev.end = cur.end;

}

}

}