Good day! It is a Friday in the month of May. The forecast called for rain and thunderstorms. We only received some rain. It is good to have some rain because things were starting to dry up. When vegetation dries up it may catch on fire.
In this post I will attempt to solve two flavors of the same problem. I believe one can create a few more problems by changing just a few words in the requirement. This will become clear as we read the requirements and describe the differences.
I found this problem named Movies on Flight in the LeetCode web site. Apparently Amazon has been using different versions on some of their technical assessments.
Question: You are on a flight and wanna watch two movies during this flight. You are given List<Integer> movieDurations which includes all the movie durations. You are also given the duration of the flight which is d in minutes. o Now, you need to pick two movies and the total duration of the two movies is less than or equal to (d - 30 min). o Find the pair of movies with the longest total duration and return their indexes. o If multiple found, return the pair with the longest movie.
The base problem starts that you are on a flight and wish to watch two movies. We are provided with a list of movie durations in minutes. The first movie would have an implicit ID of 0, the second would have an ID of 1 and so on. We are also given the flight duration.
We need to pick two movies with a total duration of flightDuration – 30 minutes. This should give us enough time to reach enough altitude to watch the entire two movies before the plane descends bellow a ceiling in which the entertainment system will be shutdown and we will be left wondering the rest of the day, how the second movie ended :o)
Our task is to find a pair of movies with the longest total duration and return their indices into the list. We need to keep in mind that if multiple pairs are found we need to return the one with the longest movie.
As a second but similar problem, we will return the closest pair of movies that match or are under the specified flightDuration – 30 minutes.
Ok, it seems we have two well defined variations of the same problem.
We will attempt to solve this problem using the Java programming language and the VSCode IDE using a Windows 10 computer. This can also be done on a Linux computer. As a matter of fact sometimes I use a Linux computer and by mistake state that I used a Windows 10 machine. VSCode seems to work well on both platforms and the resulting code should work as well after you load the JVM on your platform.
In this case I was not able to locate the actual problem on LeetCode. So we will not have a set of test cases we can pass in order for our solution to be accepted. The test cases you see come from the original LeetCode post and some that I created to verify some end conditions.
List<Integer> moviesOnFlight(List<Integer> movieDurations, int flightDuration) {
}
The signature of the method in question seems to match the requirements. We are provided the list of movie durations and the flight duration.
1, 10,25, 35,60
90
main <<< movieDurations: [1, 10, 25, 35, 60]
main <<< flightDuration: 90 (60)
moviesOnFlight0 <<< mapDurationID: {1=[0], 35=[3], 25=[2], 10=[1], 60=[4]}
main <<< exact: [3, 2] (60)
moviesOnFlight <<< clone: [1, 10, 25, 35, 60]
main <<< aprox: [2, 3] (60)
90,85,75,60,120,150,125
250
main <<< movieDurations: [90, 85, 75, 60, 120, 150, 125]
main <<< flightDuration: 250 (220)
moviesOnFlight0 <<< mapDurationID: {85=[1], 150=[5], 120=[4], 90=[0], 75=[2], 60=[3], 125=[6]}
main <<< exact: [-1, -1]
moviesOnFlight <<< clone: [60, 75, 85, 90, 120, 125, 150]
main <<< aprox: [0, 6] (215)
90,17,60,10,95,25,45,30
120
main <<< movieDurations: [90, 17, 60, 10, 95, 25, 45, 30]
main <<< flightDuration: 120 (90)
moviesOnFlight0 <<< mapDurationID: {17=[1], 25=[5], 90=[0], 10=[3], 60=[2], 45=[6], 30=[7], 95=[4]}
main <<< exact: [7, 2] (90)
moviesOnFlight <<< clone: [10, 17, 25, 30, 45, 60, 90, 95]
main <<< aprox: [7, 2] (90)
60
40
main <<< movieDurations: [60]
main <<< flightDuration: 40 (10)
main <<< exact: [-1, -1]
main <<< aprox: [-1, -1]
50,30,40
60
main <<< movieDurations: [50, 30, 40]
main <<< flightDuration: 60 (30)
moviesOnFlight0 <<< mapDurationID: {50=[0], 40=[2], 30=[1]}
main <<< exact: [-1, -1]
moviesOnFlight <<< clone: [30, 40, 50]
main <<< aprox: [-1, -1]
50,80,30,40,20
90
main <<< movieDurations: [50, 80, 30, 40, 20]
main <<< flightDuration: 90 (60)
moviesOnFlight0 <<< mapDurationID: {80=[1], 50=[0], 20=[4], 40=[3], 30=[2]}
main <<< exact: [4, 3] (60)
moviesOnFlight <<< clone: [20, 30, 40, 50, 80]
main <<< aprox: [4, 3] (60)
90, 85,75,60, 120, 150, 125
250
main <<< movieDurations: [90, 85, 75, 60, 120, 150, 125]
main <<< flightDuration: 250 (220)
moviesOnFlight0 <<< mapDurationID: {85=[1], 150=[5], 120=[4], 90=[0], 75=[2], 60=[3], 125=[6]}
main <<< exact: [-1, -1]
moviesOnFlight <<< clone: [60, 75, 85, 90, 120, 125, 150]
main <<< aprox: [0, 6] (215)
0,85,75,60,155,150,125
250
main <<< movieDurations: [0, 85, 75, 60, 155, 150, 125]
main <<< flightDuration: 250 (220)
moviesOnFlight0 <<< mapDurationID: {0=[0], 85=[1], 150=[5], 75=[2], 155=[4], 60=[3], 125=[6]}
main <<< exact: [-1, -1]
moviesOnFlight <<< clone: [0, 60, 75, 85, 125, 150, 155]
main <<< aprox: [3, 4] (215)
90,85,75,60,120,110,110,150,125
250
main <<< movieDurations: [90, 85, 75, 60, 120, 110, 110, 150, 125]
main <<< flightDuration: 250 (220)
moviesOnFlight0 <<< mapDurationID: {85=[1], 150=[7], 120=[4], 90=[0], 75=[2], 60=[3], 125=[8], 110=[5, 6]}
main <<< exact: [5, 6] (220)
moviesOnFlight <<< clone: [60, 75, 85, 90, 110, 110, 120, 125, 150]
main <<< aprox: [5, 6] (220)
90,85,75,110,60,120,110,150,125
250
main <<< movieDurations: [90, 85, 75, 110, 60, 120, 110, 150, 125]
main <<< flightDuration: 250 (220)
moviesOnFlight0 <<< mapDurationID: {85=[1], 150=[7], 120=[5], 90=[0], 75=[2], 60=[4], 125=[8], 110=[3, 6]}
main <<< exact: [3, 6] (220)
moviesOnFlight <<< clone: [60, 75, 85, 90, 110, 110, 120, 125, 150]
main <<< aprox: [3, 6] (220)
30,20
90
main <<< movieDurations: [30, 20]
main <<< flightDuration: 90 (60)
moviesOnFlight0 <<< mapDurationID: {20=[1], 30=[0]}
main <<< exact: [-1, -1]
moviesOnFlight <<< clone: [20, 30]
main <<< aprox: [1, 0] (50)
Since we cannot use the LeetCode IDE we have to develop a test scaffold.
The first line contains the duration of the movies. Note on the first test that I was experimenting with having extra blank spaces in the line. I wanted to make sure I could ingest the line and create the list without issues.
The second line holds the flight duration expressed in minutes. In the first case our flight is 90 minutes long.
It seems that our test code reads the two input lines, creates the necessary arguments to be passed to the method in question.
It seems we have two methods. The first one has been named moviesOnFlight0 and the second moviesOnFlight. Note that there are a couple debug statements which will become clear when we look at the actual code.
The first method returns a pair of movie indices that matches exactly the allotted time. The second method returns a pair of movie indices that matches the flightDuration – 30 or the closest time under the specified time without exceeding it. As you can see the problems are similar but different enough.
/**
* Test scaffold.
*
* NOT PART OF SOLUTION
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** initialization ****
List<Integer> movies = null;
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** create and populate list of movie durations ****
List<Integer> movieDurations = Arrays.stream(br.readLine().trim().split(","))
.map(s -> s.replace(" ", ""))
.map(Integer::parseInt)
.collect(toList());
// **** read and extract flight duration (in minutes) ****
int flightDuration = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< movieDurations: " + movieDurations.toString());
System.out.println("main <<< flightDuration: " + flightDuration + " (" +
(flightDuration - 30) + ")");
// **** select movies ****
movies = moviesOnFlight0(movieDurations, flightDuration);
// ???? ????
if (movies.get(0) == -1 && movies.get(1) == -1)
System.out.println("main <<< exact: " + movies.toString());
else
System.out.println("main <<< exact: " + movies.toString() + " (" +
(movieDurations.get(movies.get(0)) + movieDurations.get(movies.get(1))) + ")");
// **** select movies ****
movies = moviesOnFlight(movieDurations, flightDuration);
// ???? ????
if (movies.get(0) == -1 && movies.get(1) == -1)
System.out.println("main <<< aprox: " + movies.toString());
else
System.out.println("main <<< aprox: " + movies.toString() + " (" +
(movieDurations.get(movies.get(0)) + movieDurations.get(movies.get(1))) + ")");
}
Our test scaffold reads the input values and creates the necessary arguments for the methods of interest. The methods are then called and the returned movie indices are displayed. We also display the max duration so it can help us verify the results of each method.
/**
* Find the pair of movies with the longest total duration and return their indices.
* If multiple found, return the pair with the longest movie.
*
* Exact match!!!
*/
static List<Integer> moviesOnFlight0(List<Integer> movieDurations, int flightDuration) {
// **** sanity checks ****
if (movieDurations.size() <= 1)
return Arrays.asList(-1, -1);
// **** initialization ****
Map<Integer, List<Integer>> mapDurationID = new HashMap<>();
int maxD1 = -1;
int maxD2 = -1;
int maxNdex1 = -1;
int maxNdex2 = -1;
int fd = flightDuration - 30; // for ease of use
// **** populate hash map with duration -> ID in O(n) ****
for (int i = 0; i < movieDurations.size(); i++) {
// **** get duration of this movie ****
int duration = movieDurations.get(i);
// ???? ????
// System.out.println("moviesOnFlight0 <<< i: " + i + " duration: " + duration);
// **** check if we already have this movie ****
List<Integer> lst = mapDurationID.get(duration);
// **** create new list (if needed) ****
if (lst == null)
lst = new ArrayList<Integer>();
// **** map duration and ID ****
lst.add(i);
mapDurationID.put(duration, lst);
}
// ???? ????
System.out.println("moviesOnFlight0 <<< mapDurationID: " + mapDurationID.toString());
// **** traverse list looking for pair(s) of movies in O(n) ****
for (int i = 0; i < movieDurations.size(); i++) {
// **** get duration for this movie ****
int d1 = movieDurations.get(i);
// ???? ????
// System.out.println("moviesOnFlight0 <<< i: " + i + " d1: " + d1);
// **** compute duration for second movie ****
int d2 = fd - d1;
// ???? ????
// System.out.println("moviesOnFlight0 <<< d2: " + d2);
// **** look for movie with d1 ****
List<Integer> lst1 = mapDurationID.get(d1);
// **** look for movie with d2 ****
List<Integer> lst2 = mapDurationID.get(d2);
// **** check if SAME durations (in same list) have same index ****
if (lst1.equals(lst2)) {
// ???? ????
// System.out.println("moviesOnFlight0 <<< lst2: " + lst2.toString());
// **** check if indices are the same ****
if (lst2.size() <= 1)
continue;
}
// **** found ID with d2 ****
if (lst2 != null) {
// ???? ????
// System.out.println("moviesOnFlight0 <<< lst: " + lst2.toString());
// **** check if this pair has the longest movie ****
if (d1 > maxD1 || d2 > maxD2) {
// **** update first movie ****
maxD1 = d1;
maxNdex1 = i;
// **** update second movie ****
maxD2 = d2;
if (mapDurationID.get(d2).size() <= 1)
maxNdex2 = mapDurationID.get(d2).get(0);
else
maxNdex2 = mapDurationID.get(d2).get(1);
}
}
}
// ???? ????
// System.out.println("moviesOnFlight0 <<< maxD1: " + maxD1 + " maxD2: " + maxD2);
// **** return proper indices ****
if (maxD1 == -1 || maxD2 == -1)
return Arrays.asList(-1, -1);
else
return Arrays.asList(maxNdex1, maxNdex2);
}
In this attempt we need to return an exact match such that duration1 + duration2 == flightDuration – 30. Any things else must return a pair of -1 values.
We perform some sanity checks and initialization.
In the first loop O(n) we populate a hash map to map the movie duration to the ID which is the index in the provided list.
In the second loop we traverse the list looking for pairs that match the flight duration (-30). The idea is to compute the expected pair and look for it in the hash map.
When all is said and done we return the pair of movies if found or a pair as a list with values -1 each.
/**
* Find the pair of movies with the longest total duration and return they indices.
* If multiple found, return the pair with the longest movie.
*
* Less than or equal match !!!
*/
static List<Integer> moviesOnFlight(List<Integer> movieDurations, int flightDuration) {
// **** sanity checks ****
if (movieDurations.size() <= 1)
return Arrays.asList(-1, -1);
// **** initialization ****
int fd = flightDuration - 30; // for ease of use
int m1 = -1;
int m2 = -1;
int dev = Integer.MAX_VALUE;
int i = 0;
int j = movieDurations.size() - 1;
// **** clone the movie durations ****
List<Integer> clone = new ArrayList<Integer>(movieDurations);
// **** sort clone of movie durations O(nlog(n)****
Collections.sort(clone);
// ???? ????
System.out.println("moviesOnFlight <<< clone: " + clone);
// **** loop looking for pair closest to d in O(n)****
while (i <= movieDurations.size() - 1 && j >= 0 && i < j) {
// ???? ????
// System.out.println("moviesOnFlight <<< i: " + i + " j: " + j);
// **** compute time for both movies ****
int time = clone.get(i) + clone.get(j);
// ???? ????
// System.out.println("moviesOnFlight <<< time: " + time);
// **** compute time difference ****
int diff = fd - time;
// ???? ????
//System.out.println("moviesOnFlight <<< diff: " + diff);
// **** time exceeded :o( ****
if (diff < 0) {
j--;
}
// **** time less than flight time - 30 minutes :o) ****
else if (diff > 0) {
// **** check if we already have a pair with same difference ****
if (diff == dev) {
// **** ****
if (clone.get(m1) < clone.get(i) ||
clone.get(m2) < clone.get(j)) {
dev = diff;
m1 = i;
m2 = j;
}
}
// **** check if these movies are closer to our goal ****
else {
// **** update the remain and save these movies ****
if (diff < dev) {
dev = diff;
m1 = i;
m2 = j;
}
}
// ???? ????
// System.out.println("moviesOnFlight <<< dev: " + dev);
// **** ****
i++;
}
// **** found movies that meet exact flight time - 30 :o) ****
else {
// // ???? ????
// System.out.println("moviesOnFlight <<< i: " + i + " j: " + j);
// System.out.println("moviesOnFlight <<< m1: " + m1 + " m2: " + m2);
// **** ****
int d1 = clone.get(i);
int d2 = clone.get(j);
// // ???? ????
// System.out.println("moviesOnFlight <<< d1: " + d1 + " d2: " + d2);
// **** map movies to initial locations ****
m1 = movieDurations.indexOf(d1);
m2 = movieDurations.lastIndexOf(d2);
// **** ****
return Arrays.asList(m1, m2);
}
}
// ???? ????
// System.out.println("moviesOnFlight <<< m1: " + m1 + " m2: " + m2);
// **** check if pair not found ****
if (m1 == -1 && m2 == -1)
return Arrays.asList(-1, -1);
// **** map movies to initial locations ****
m1 = movieDurations.indexOf(clone.get(m1));
m2 = movieDurations.indexOf(clone.get(m2));
// **** ****
return Arrays.asList(m1, m2);
}
In this case we must return a perfect match of the largest match under the flight time (-30).
We perform sanity checks and initialize variables. Note that in this case we will not use a hash map. We will use two indices. We will converge from each side of a sorted list (we could have used an array). Remember that the input data is not sorted so we will have to sort the list in order O(n log(n)).
Note that we could sort the input list and will change the order of the elements. In this case that is not important, but in production we could induce side effect(s). For this reason we make a clone of the list and then sort the clone.
Now we enter a loop in which we will move into the best possible solution.
We compute the time for the movies in this pass. We then compute the difference between the time and the flight duration. Keep in mind that our result must match the flight duration (- 30) or be the largest closer value not exceeding the flight duration (-30).
We then proceed using the diff variable. If the time has been exceeded we move j left (movie pair too long).
We then check if the time is under the flight duration (-30). Remember that we need to get the largest value under the flight duration (-30). The difference and the movie indices are updated as need.
The last possibility is that our pair matches exactly the flight duration (-30). Note that we use the sorted clone which does not have the proper movie indices because we sorted them. We need to map them back to the indices in the movieDurations list. The proper indices are returned as a pair in a list.
If we complete the loop, we have not found a perfect match with the flight time (-30). Se we need to repeat the process we saw when a perfect match was found and return the pair of movie indices with the closest value but no exceeding the flight duration (-30).
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John