The lexicographically minimum permutation subject to interval constraints

Правка en1, от Roundgod, 2023-06-28 14:38:47

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!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Roundgod 2023-06-28 14:38:47 739 Initial revision (published)