I was recently puzzled by this problem:

• Given $$$n$$$ intervals $$$[l_i,r_i]$$$. Find the lexicographically minimum permutation $$$p_1,p_2,\dots,p_n$$$ of $$$1-n$$$ such that $$$p_i\in [l_i,r_i]$$$ for each $$$1\leq i\leq n$$$.

This problem comes from misreading the problem A Place For My Head from Petrozavodsk Summer 2017. Day 5. Moscow IPT Contest. The original problem requires that $$$q_i\in [l_i,r_i]$$$ where $$$q=p^{-1}$$$ is the inverse permutation of $$$p$$$ and has constraint $$$1\leq n\leq 2\times 10^5$$$.

I wonder if there exists a decent (subquadratic) solution for this (misread version) of the problem? Many thanks in advance!