Last Updated: 27 Apr, 2021
Movies Time
Moderate
Asked in company
Bucky and Steve love movies. Due to lockdown everywhere, they have enough time to see movies together. So they decided to rent the movies online to watch them. But due to some policies of the movie’s website, they cannot rent the same movie together. So they decided to watch it separately.
They choose ‘N’ movies to watch. The duration of each movie is given in a list of ‘MOVIES’. They want to finish the set of ‘N’ movies as soon as possible. You have to find the minimum time they need to watch ‘N’ movies if both cannot watch the same movie at the same time.
Input Format :
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case contains an integer ‘N’ representing the number of movies.
The second line contains ‘N’ space-separated integers denoting the time required to watch these ‘N’ movies.
Output Format :
For each test case, print the minimum time required for Bucky and Steve to watch ‘N’ movies under the given conditions.
Output for every test case will be printed in a separate line.
Note :
You don’t need to print anything; It has already been taken care of.
Constraints :
1 <= T <= 50
1 <= N <= 10^6
1 <= MOVIES[i] <= 10^9
Where 'MOVIES[i]’ is the duration of the ‘i-th’ movie.
Time limit: 1 sec.
Approaches
The basic idea of finding minimum time is to check if the maximum element is greater than the sum of the rest of the elements in the array. The minimum time required will be twice the maximum element. As when one of them is watching the movie with the maximum time duration, the other can complete the rest of the movies in the same time. Similarly, when the second one watches that longest movie, the first one can watch the rest of the movies.
The other case will be when the maximum element is less than the sum of all others. Then there will be only one optimal option, i.e., one of them will watch the movie in increasing order of time duration, and the other will watch it in decreasing order of time duration. In this case, the answer will be the sum of the time duration of all the movies.
Algorithm
- Declare and Initialize a variable ‘LARGEST’ = 0 to store the value of the movie with maximum duration. It will be of type int.
- Declare and Initialize a variable ‘SUM’ = 0 to store the sum of the elements of the ‘MOVIES’ array.
- Iterate from 0 to ‘N’ in the ‘movies’ array. (let the iterator be ‘i’)
- Update ‘SUM’ as ‘SUM’ += ‘MOVIES[i]’.
- Maximize ‘LARGEST’ by ‘LARGEST' = max(‘LARGEST’, ‘MOVIES[i]’)
- If ‘SUM’ - ‘LARGEST’ is less than ‘LARGEST’, then return 2* ‘LARGEST’
- Else return ‘SUM’.