Least number of days required to finish watching all movies given durations array if you can watch maximum 3.00 duration movie per day

Question

Input: double array representing duration of movies e.g. durations[] ={1.01, 2.4, 1.01, 1.01, 1.4}. You can watch maximum 3.00 duration movie per day.
Find the least number of days needed to finish watching all the movies.
Constraint: 1.01 <= duration[i] <= 3.00.
(You can choose to watch any movie on a day and won't repeat watching a movie)

Sample Test Cases:
Input: duration[] = {1.01, 2.4, 1.01, 1.01, 1.4} Output: 3
Input: duration[] = {1.01, 2.4, 1.4, 1.6, 2.6, 1.7} Output: 4
Input: duration[] = {1.01, 2.4, 1.5, 1.6, 2.6, 1.7} Output: 5

I got this in a placement coding test and couldn't finish it on time but did it later using recursion. It worked with few test cases I custom made but I'm not not sure if it will work for all possible test cases. Also I feel it could be enhanced for better time complexity. Kindly help.

My insight: You would be able to watch max 2 movies a day as durations are always >= 1.01 so watching any 3 movies would make duration exceed 3.00.

Here's my code:

import java.util.ArrayList;

public class MoviesBetterSolution {

      public static void main(String[] args) {

           double arr[] = {2.0,1.01,1.4,2.4,1.71};  //test case

           System.out.println( f( 0, 0.00 , 1, 3.00,  new ArrayList<Integer>(),  arr , 0) ); 
           //days passed a 1 as we start from day 1
           //initial wtn (watched till now for a particular day) passes is 0.00

    }   static int minDays = Integer.MAX_VALUE;

    //wtn -> watched till now (keeps track of duration of movies watched on the current day
    //taken keeps track of number of movies watched on current day
    // picked : watched movies on the day till now  private static int f(int i, double wtn, int days, double limit,  ArrayList<Integer>
picked, double[] arr, int taken) {

          //updating minDays after reaching a point where all movies have been watched

            if(picked.size()==arr.length) {
                   if( days<minDays ) minDays = days;
                   return minDays;  
            }
           if(i == arr.length) {  //finished traversing array
             if(taken != 0) {     //restart traversing to watch unwatched movies only if atleast 1 
                       //movie was watched on the day, setting taken for the new traversal to be 0
                      i = 0;         
                      taken = 0;            }else {       // otherwise just return if nothing was watched on the day, otherwise it 
                              //will stackoverflow for all non watch choice recursion branch
                        return minDays;`            }       }
                if((wtn + arr[i] <= limit) && !(picked.contains(i)) ) {  //only movies that havent been watched can be watched
            
               ArrayList<Integer> temp = new ArrayList<Integer>();
               temp = (ArrayList<Integer>) picked.clone();
               temp.add(i);
               if(taken<2) { //as u can watch only 2 movies a day
                   f(i+1, wtn + arr[i] , days, limit, temp, arr, taken+1);  //watch & move to next movie but on same day            }
                        f(0, 0 , days +1 , limit, temp, arr, taken+1);  // watch & move to next movie but on next day , wtn and index(i) set to 0 as u
starting new day        }
     
             f(i+1, wtn, days, limit, picked, arr, taken); //not watch & move to next movie on same day

              return minDays;   } }

Answer 1

Assuming all movies have run times between 1.01 and 3.00, solve this in O(n log n)

1. sort your list
2. set days = 0
3. set two pointers to the two ends of your list.
4. repeatedly do the following until all elements have been processed:
4.1 increment days
4.2 if the sum of the movies referred to is <= 3.0 then move both pointers towards the center, otherwise just decrement the larger one.

Just before the end, it's possible that both pointers refer to the same element. That takes a day.