Scheduling a sequence of queue operations that push and pop items at specified times

Question

What is the time complexity of the following problem?

Definitions

A FIFO is a queue functional unit supporting four commands: PUSH (data to back of queue), POP (the head of the queue), PNP (POP the head of queue and PUSH it to the back), NOP (do nothing). Each command takes one unit of time to execute.

FIFO code (or a schedule of commands) is a sequence of commands to execute.

Problem Description

We are given $n$ items of data $T_1,\dots,T_n$, and $n$ triplets $(T_1,t^{in}_1,t^{out}_1),\dots,(T_n,t^{in}_n,t^{out}_n)$. $t^{in}_i$ and $t^{out}_i$ identify the time when $T_i$ is PUSHed and POPed respectively. We're guaranteed that $t^{in}_i<t^{out}_i$ for every $i$ and $t^{in}_i,t^{out}_i$ are all unique.

The goal is to produce FIFO code (a schedule of commands) that push each $T_i$ at time $t^{in}_i$ and pop it at time $t^{out}_i$, by adding NOP and PNP commands between the PUSH and POP commands given. No extra PUSH or POP commands can be added: the resulting code must contain exactly $n$ PUSHes and $n$ POPs.

Example

Input: $(T_1,2,4)$, $(T_2,1,5)$

Solution:

1. PUSH $T_2$
2. PUSH $T_1$
3. PNP
4. POP // T_1
5. POP // T_2

Answer 1

Initial Direction

Solving this problem is equivalent to solving a set of equations with constraints.

Denote the number of time units in an interval between consecutive input $t^{in}_i$/$t^{out}_i$ by $K_i$.

In the above example in the question there are three intervals:

|PUSH($T_2$) | PUSH($T_1$)|---------------|POP($T_1$) |POP($T_2$)|

|---------------|---------------|---------------|---------------|---------------|

1. $K_1=0$.
2. $K_2=1$.
3. $K_3=0$.

The depth of the FIFO at the beginning and end of each such interval is the number of PUSHs minus POPs made before it, denote it by $d_i$.

In the above example:

1. $d_0=0$.
2. $d_1=1$.
3. $d_2=2$.
4. $d_3=1$.

Denote by $x_i\in \mathbb{N}\cup\{0\}$ the number of PNP assigned in interval $K_i$, then $x_i\leq K_i$.

In the above example:

1. $x_1\leq 0$.
2. $x_2\leq 1$.
3. $x_3\leq 0$.

Per data unit $T_i$ add an equation asserting it is available at the head of the FIFO at time $t^{out}_i$ by adding $d_i+x_{i+1}$ modulo the depth, $d_{i+1}$ of the FIFO per interval. In the above example:

1. For $T_1$: $(1+x_2)\bmod 2=0$.
2. For $T_2$: $((( (0+x_1)\bmod 1+x_2 ) \bmod 2)+x_3) \bmod 1 =0$.

And the solution is $x_1=0, x_2=1, x_3=0$ corresponding with the solution above.

But I'm not sure how to use this information to understand the complexity of the problem.

Answer 2

In the worst case,

The element at the tail of the queue need to be popped i.e.,

Given n units of data and n triplets

If n = 4 (number of element in the queue and number of triplets are four)

Input: (T₁, 1, 14), (T₂, 2, 13), (T₃, 3, 11), (T₄, 4 ,8)

At time 4 the state of the queue:

╔══════════════════════════════╗
║            QUEUE             ║
╠══════╤══════╤════╤════╤══════╣
║      │ Head │    │    │ Tail ║
╟──────┼──────┼────┼────┼──────╢
║ DATA │  T1  │ T2 │ T3 │  T4  ║
╚══════╧══════╧════╧════╧══════╝

At time 5, T₄ should be popped and to do that all the element left to T₄ should be PNP (here, three PNP).

PNP (POP the head of queue and PUSH it to the back)

That is, (n-1) elements of the queue should be PNP to pop n^th element from the queue.

At time 7 the state of the queue:

╔══════════════════════════════╗
║            QUEUE             ║
╠══════╤══════╤════╤════╤══════╣
║      │ Head │    │    │ Tail ║
╟──────┼──────┼────┼────┼──────╢
║ DATA │  T4  │ T1 │ T2 │  T3  ║
╚══════╧══════╧════╧════╧══════╝

At time 8 the state of the queue (pop T₄):

╔═════════════════════════════╗
║            QUEUE            ║
╠══════╤═══╤══════╤════╤══════╣
║      │   │ Head │    │ Tail ║
╟──────┼───┼──────┼────┼──────╢
║ DATA │ - │  T1  │ T2 │  T3  ║
╚══════╧═══╧══════╧════╧══════╝

As we go on, we can see for popping one element at the tail requires to PNP all the element right of it.

Gives,

╔══════════════════════╤════════════════════════╗
║ Element to be popped │ Number of NPN required ║
╠══════════════════════╪════════════════════════╣
║          n           │          n-1           ║
╟──────────────────────┼────────────────────────╢
║         n-1          │          n-2           ║
╟──────────────────────┼────────────────────────╢
║          .           │           .            ║
╟──────────────────────┼────────────────────────╢
║          .           │           .            ║
╟──────────────────────┼────────────────────────╢
║          2           │           1            ║
╟──────────────────────┼────────────────────────╢
║          1           │           0            ║
╚══════════════════════╧════════════════════════╝

Thus, in worst case we have a total

= n-1 + n-2 + n-3 + ... + 2 + 1

= [ n ( n + 1 ) ] / 2 - n

= n² + n

= O( n² )

Answer :

Worst case time complexity of the problem = O( n² )

Best case time complexity of the problem = O( 1 ) // when an element is requested to pop, it is found at the head of the queue.