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).
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.
T may contain tasks with duration more than
L, but it is guaranteed to contain at least one task with duration at most
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.
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.
[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
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.
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