Scheduling a sequence of queue operations that push and pop items at specified times 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&lt;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:


PUSH $T_2$
PUSH $T_1$
PNP
POP // T_1
POP // T_2
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$)|

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


$K_1=0$.
$K_2=1$.
$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:


$d_0=0$.
$d_1=1$.
$d_2=2$.
$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:


$x_1\leq 0$.
$x_2\leq 1$.
$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:


For $T_1$: $(1+x_2)\bmod 2=0$.
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.