This answer presents two algorithms. The first uses flow network. The second, a faster algorithm, takes advantage of "ranges".
This problem can be solved using a unit capacity flow network (and Dinic's algorithm).
In order to transform the problem into a unit capacity flow network problem, we need to do the following:
- Make a node $v_i$ for every item $i$.
- Make a node $w_j$ for every position in the list $j$.
- Add an edge $e = (v_i,w_j)$ if item $i$ is allowed to go into position $j$.
- Add two nodes $s,t$ such that for every $i$, there is an edge $(s, v_i)$, and for every $j$, there is an edge $(w_j,t)$.
- All edges have capacity $1$.
The final graph is a unit capacity graph, and running Dinic's algorithm on it will return a max flow solution.
The max flow solution can be converted back to a solution of the original problem, by placing item i in slot j if there is flow between vi and wj.
Note: This algorithm will take $O(n^2)$ to convert to a flow network, and in the worst case Dinic's algorithm will take $O(n^{2.5})$, so the overall the time complexity is $O(n^{2.5})$.
Note: this algorithm misses a full proof to its correctness. please complete it if you manage to prove it
I noticed that you specifically use ranges and we could take advantage of that fact.
The algorithm:
- Sort all of the given ranges by their length (which means that $[5,6]$ comes before $[3,9]$ for example). let that sorted list be called R
- For every range $[i,j]$ in R:
- Find the first empty slot between i and j, and place the corresponding item there. if no empty slot was found, return NO_SOLUTION
Complexity analysis:
Sorting takes $O(n\log n)$ time, and iterating through R takes $O(n)$, but every iteration can take (W.C) up to $O(n)$.
Overall $O(n\log n) + O(n^2) = O(n^2)$
Truth proof:
let us split the proof to soundness and completeness:
soundness (if algorithm returns something, it is valid):
pretty obvious since it only places items at legal free spots, thus if it will return something - its going to be correct.
completeness (if there is a solution, the algorithm will not return NO_SOLUTION): MISSING