"Finish work" as early as possible

Question

Background

Imagine for a moment that you have a mind-numbingly boring job. Every morning, you are given a collection of tasks that you should work on that day. Each task has a certain duration, and once started, it must be completed in one go. Your boss will not tolerate idling, so if there are tasks that you could still complete before going home, you must work on one of them (you can choose which one). Conversely, if all remaining tasks would require you to work overtime, you get to go home early! Thus your goal is to minimize the length of your workday by clever scheduling.

Fun fact: this is one variant of the lazy bureaucrat scheduling problem, and it is NP-hard (source).

Input

You have two inputs: the number of "time units" in your workday (a positive integer L), and the collection of tasks (a non-empty array of positive integers T, representing task durations). They can be taken in any order, and in any reasonable format. The array T may contain tasks with duration more than L, but it is guaranteed to contain at least one task with duration at most L.

Output

A valid schedule is a subset of tasks S ⊆ T such that sum(S) ≤ L, and every task not in S (counting multiplicities) has duration strictly more than L - sum(S). Your output shall be the smallest possible sum of a valid schedule. In other words, you shall output the minimal number of time units you must work today.

Example

Consider the inputs

L = 9
T = [3,4,4,4,2,5]

One way of scheduling your day is [4,4]: you finish two tasks in 8 time units, and have 1 unit left. Since no 1-unit tasks are available, you can go home. However, the schedule [2,5] is even better: you work for 7 time units, and then all remaining tasks would take 3 or more time units. The schedule [2,4] is not valid, since after working for 6 time units, you'd still have enough time to finish the 3-unit task. 7 units turns out to be optimal, so the correct output is 7.

Rules and scoring

You can write either a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. There is no time bound, so brute forcing is perfectly acceptable.

Test cases

These are given in the format L T -> output.

 1 [1,2] -> 1
 6 [4,1] -> 5
 7 [7,7,9] -> 7
 9 [3,4,4,4,2,5] -> 7
20 [6,2,3,12,7,31] -> 17
42 [7,7,7,7,8,8,8] -> 36
42 [7,7,7,7,7,8,8,8] -> 35
42 [7,7,7,7,7,7,8,8,8] -> 36
16 [1,2,3,4,5,6,7,8,9,10] -> 13
37 [15,27,4,1,19,16,20,26,29,18] -> 23
22 [24,20,8,8,29,16,5,5,16,18,4,9] -> 18
80 [10,22,11,2,28,20,27,6,24,9,10,6,27,2,15,29,27] -> 71
59 [26,28,5,4,7,23,5,1,9,3,7,15,4,23,7,19,16,25,26] -> 52

Answer 1

Jelly, 20 bytes

³œ-;⁴Ṃ;¹S>⁴
ŒPÇÐfS€Ṃ

Try it online!

TIO is fast enough to finish the last test cases within its 60 second time limit, even if just barely.

Background

The algorithm is both simple and inefficient:

1. We generate all subsets of T, counting multiplicities.

2. We filter the the subsets, keeping only those those subsets S that satisfy one of the following criteria:

   • S is different from T, and the sum of the elements of S and the minimal element not in S is larger than L.

   • S and T are identical.

   The filtered T (let's call it T') now contains all lists of task that do just enough work (or even some overtime).

3. Of all S in T', pick the one with the lowest sum.

How it works

ŒPÇÐfS€Ṃ     Main link. Left input: T (list). Right input: L (integer).

ŒP           Powerset; generate all subsets of T.
   Ðf        Filter them...
  Ç            applying the helper link.
     S€      Compute the sum of each kept subset.
       Ṃ     Take the minimum.

³œ-;⁴Ṃ;¹S>⁴  Helper link. Input: A (subset of T)

³œ-          Multiset subtraction; remove the elements of A from T, counting
             multiplicities.
   ;⁴        Append L to the resulting list.
     Ṃ       Take the minimum.
             If S == T, the difference was empty and the minimum is L.
      ;¹     Prepend the minimum to A.
        S    Compute the sum.
         >⁴  Compare it with L.
             If S == T, the comparison will return 1.

Answer 2

Pyth, 26 25 bytes

JEhSsMf&gJsT>hS.-QT-JsTyQ

Try it online. Test suite.

I haven't been able to run the last two test cases (they time out online, I assume), but all the others work. This is just a basic brute force solution.

Answer 3

Ruby, 124 bytes

->(m,s){
f=proc{|l,t|t.reject!{|x|x>l}
(0...(t.size)).map{|x|
f.call(l-t[x],t[0,x]+t[(x+1)..-1])
}.max||l
}
m-f.call(m,s)
}

This is a brute-force solution.

Answer 4

MATL, 36 bytes

iTFinZ^!"2G@2#)sXKt1G>~wb+lG>A*?KhX<

Try it online!

i           % input number L
TF          % array [true, false]
in          % input array T. Get its length
Z^!         % Cartesian power and transpose. Each column is a selection from T
"           % for each selection
  2G@2#)    %   take non-selected and then selected tasks
  sXK       %   sum of selected tasks. Copy to clipboard K
  t1G>~     %   duplicate. Is sum of selected tasks <= L?
  wb        %   swap, rotate
  +         %   sum of selected tasks plus each non-selected task
  lG>A      %   are all of those numbers greater than L?
  *         %   are both conditions met?
  ?         %   if so
    Kh      %     paste current minimum (or initially L), append new value
    X<      %     compute new minimum
            %   end if implicitly
            % end for each implicitly
            % display stack implicitly