First, the problem discription:For a sequence of $4n$ tasks, $a_1a_2\dots a_{4n}$, where $a_i\in\{0,1\}\forall i$, put them sequentially to the tail of one of the two initially empty queues of length $0$ such that in the end all the tasks are put in the queues and both queues has length $2n$. Let $cost$ be 0 at first. For each task $a_i$ that has value $1$, we add its index in the queue to the $cost$.The objective is to minimize the $cost$.Example, the sequence of tasks is $10101010$, and we put the $1$th task in queue $1$, the $2$th task in queue $1$, the $3$th task in queue $2$, the $4$th task in queue $1$, the $5$th task in queue $2$, the $6$th task in queue $1$, $7$th task in queue $2$, the $8$th task in queue $2$, then queue $1$ will has task sequence $1000$ and queue $2$ will has task sequence $1110$, so the $cost$ is $(1)+(1+2+3)=7$.Then we describe the greedy algorithm with parameter $0\le k\le 2n$It first puts the first $k$ tasks sequentially to the end of queue $1$. Then for $i=k+1,\dots$, if $a_i=1$ it puts the $i$th task into a queue with smaller length, else it puts the $i$th task into a queue with bigger length until one of the queues is full(it has length $2n$). Finally it puts the rest of tasks sequentially to the end of the non-full queue.The question is proving the best greedy algorithm(over choices of $k$) gives the optimal cost for any $4n$ length sequence. I have many simulation results that support this statement and haven't found a proof yet.
Proving greedy algorithm is optimal for a scheduling problem
ds.algorithms;optimization;lower bounds;proofs;scheduling