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