Movies Time

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
0 upvote
Asked in company
Adobe

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1 :
2
3
2 3 8
3
2 3 4
Sample Output 1 :
16
9
Explanation For Sample Input 1 :
Here in the first test case, Bucky will start watching a movie of 8 minutes while Steve will watch 2 and 3 minutes. So it will take 8 minutes as both are watching simultaneously, then this process will be reversed. So it takes a total of 8+8 = 16 minutes.

In the second test case Bucky will watch movies in the order 1 -> 2 -> 3 and Steve will watch movies in the order 3 -> 1 -> 2. When Bucky will end his 3rd movie then Steve’s movie will also be finished.
So the answer will be 2+3+4 = 9.
Sample Input 2 :
2
3
7 6 4
4
1 4 2 6
Sample Output 2 :
17
13
Hint

Can you think of a solution by finding a pattern to minimize the time.

Approaches (1)
Greedy Algorithm

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’.
Time Complexity

O(N), where ‘N’ is the size of the ‘MOVIES’ array.

 

We are iterating once to find the sum of the array and maximum value in the array. So the overall time complexity will be O(N).

Space Complexity

O(1)

 

Constant extra space is used.                    

Code Solution
(100% EXP penalty)
Movies Time
Full screen
Console