fundo

Imagine por um momento que você tem um trabalho entediante. Todas as manhãs, você recebe uma coleção de tarefas nas quais deve trabalhar naquele dia. Cada tarefa tem uma certa duração e, uma vez iniciada, deve ser concluída de uma só vez. Seu chefe não tolerará ociosidade; portanto, se houver tarefas que você ainda possa concluir antes de voltar para casa, trabalhe em uma delas (você pode escolher qual delas). Por outro lado, se todas as tarefas restantes exigirem que você faça horas extras, você poderá voltar para casa mais cedo! Assim, seu objetivo é minimizar a duração do seu dia de trabalho com agendamento inteligente.

Curiosidade: essa é uma variante do problema de agendamento do burocrata preguiçoso e é difícil para o NP ( fonte ).

Entrada

Você tem duas entradas: o número de "unidades de tempo" em seu dia de trabalho (um número inteiro positivo L) e a coleção de tarefas (uma matriz não vazia de números inteiros positivos T, representando a duração da tarefa). Eles podem ser obtidos em qualquer ordem e em qualquer formato razoável. A matriz Tpode conter tarefas com duração maior que L, mas é garantido que contenha pelo menos uma tarefa com duração no máximo L.

Saída

Um agendamento válido é um subconjunto de tarefas S ⊆ Tque sum(S) ≤ L, e todas as tarefas que não estão S(contando multiplicidades) têm duração estritamente maior que L - sum(S). Sua saída deve ser a menor soma possível de uma programação válida. Em outras palavras, você deve gerar o número mínimo de unidades de tempo que deve trabalhar hoje.

Exemplo

Considere as entradas

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

Uma maneira de agendar seu dia é [4,4]: você termina duas tarefas em 8 unidades de tempo e resta 1 unidade. Como não há tarefas de 1 unidade disponíveis, você pode ir para casa. No entanto, a programação [2,5]é ainda melhor: você trabalha por 7 unidades de tempo e todas as tarefas restantes levam 3 ou mais unidades de tempo. O agendamento [2,4]não é válido, pois depois de trabalhar por 6 unidades de tempo, você ainda terá tempo suficiente para concluir a tarefa de 3 unidades. 7 unidades são ideais, portanto a saída correta é 7.

Regras e pontuação

Você pode escrever um programa completo ou uma função. A menor contagem de bytes vence e as brechas padrão não são permitidas. Não há tempo limitado, portanto forçar brutalmente é perfeitamente aceitável.

Casos de teste

Estes são dados no formato 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

Gelatina, 20 bytes

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

Experimente online!

O TIO é rápido o suficiente para concluir os últimos casos de teste dentro do seu prazo de 60 segundos, mesmo que apenas por pouco.

fundo

O algoritmo é simples e ineficiente:

1. Geramos todos os subconjuntos de T , contando multiplicidades.

2. Nós filtramos os subconjuntos, mantendo apenas aqueles subconjuntos S que atendem a um dos seguintes critérios:

   • S é diferente de T , e a soma dos elementos de S e o elemento mínimo não em S é maior do que L .

   • S e T são idênticos.

   O T filtrado (vamos chamá-lo de T ' ) agora contém todas as listas de tarefas que funcionam apenas o suficiente (ou mesmo algumas horas extras).

3. De todos os S em T ' , escolha o que tiver a menor soma.

Como funciona

Œ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.

Pitão, 26 25 bytes

JEhSsMf&gJsT>hS.-QT-JsTyQ

Experimente online. Suíte de teste.

Não fui capaz de executar os dois últimos casos de teste (eles esgotam o tempo online, suponho), mas todos os outros funcionam. Esta é apenas uma solução básica de força bruta.

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)
}

Esta é uma solução de força bruta.

MATL , 36 bytes

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

Experimente 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