Classificando uma pilha não ordenada de itens em gavetas com movimentos mínimos da gaveta

Há um tempo atrás, eu lavava minhas roupas tarde da noite. Quando trouxe minha roupa de volta ao meu dormitório, comecei a guardá-la.

Meu guarda-roupa está configurado da seguinte maneira:

• Minhas gavetas são categorizadas pelo tipo de roupa que eles têm, e eu sou muito especial nisso; isso significa que não posso colocar camisetas na gaveta da minha calça (caso contrário, ficarei muito perturbada com isso para dormir). É claro que conheço essa categorização e sei qual gaveta é qual mesmo no escuro.
• eu tenho $N$ peças de roupa limpas e $M$ gavetas dispostas verticalmente (com a gaveta na parte superior $D_0$)
• Posso abrir e fechar gavetas como achar melhor, mas se a gaveta $D_i$ está aberto, não consigo colocar roupas na gaveta $D_{i+1}$ (porque está bloqueado por $D_i$)
• Todas as minhas gavetas já estão fechadas quando entro na sala.
• Quando terminar, tenho que fechar todas as gavetas abertas.

Considerável cavalheiro que sou, não quero acordar meu colega de quarto (era um dormitório da faculdade, por isso dormimos no mesmo quarto). Resolvi não acender as luzes e fazer o mínimo de barulho possível.

Isso significa que eu tenho que guardar minhas roupas nas seguintes restrições:

• Não consigo ver a minha bolsa de roupa suja, então só sei o que pego assim que a puxo.
• Abrir e fechar uma gaveta faz barulho. Puxar itens da minha bolsa de roupas ou colocá-los na gaveta não é o caso.
• Só posso guardar uma peça de roupa de cada vez; Não posso dobrar como roupas e colocá-las em pilhas (e depois guardá-las) porque o chão está muito sujo e não há espaço nos móveis ao meu alcance.
• Posso colocar uma peça de roupa de volta na minha bolsa e tirar outra, mas a que eu tirar a seguir pode ser a que acabei de colocar (lembre-se, não tenho controle sobre o que retiro da bolsa).

Diante disso, tenho três perguntas:

• Como posso guardar minhas roupas enquanto abro e fecho as gavetas o menor número de vezes possível?
• Alguém mais pensou nesse problema ou em algo semelhante?
• Esse problema tem aplicações práticas?

Que tal o seguinte:

1. Passe pela sua bolsa; dobrar e empilhar itens para gavetas$D_i$ e $D_{i+1}$, $i \in 2\mathbb{N}$, na gaveta $D_i$ (que você abre sob demanda).

   Verifique se você possui os itens para $D_{i+1}$em cima; isso pode exigir bastante reorganização no estilo de panqueca , mas você não parece preocupado com essas operações.

   Observe que sempre há espaço suficiente (duas alturas de gaveta) para fazer isso, supondo que as gavetas sejam aproximadamente iguais e que suas roupas se encaixem nelas como estão.

2. Para cada gaveta aberta $D_i$,

   • pegue a pilha para $D_{i+1}$ (e coloque na bolsa, se necessário),
   • Fechar $D_i$,
   • aberto $D_{i+1}$,
   • coloque a pilha lá dentro e
   • Fechar $D_{i+1}$.

Este algoritmo requer $2M$ movimentos das gavetas, se todas as gavetas tiverem roupas, por isso é o pior caso.

Desperdiçará alguns movimentos se houver itens para $D_{i+1}$ mas não $D_i$; se apenas gavetas ímpares obtiverem itens, executamos o dobro dos movimentos necessários. Como isso é o pior que pode acontecer, ainda temos uma$2$-aproximação.