$(20$ pts$)$ Suppose we are given two arrays $x[1..n]$ and $y[1..n]$ of integers. We would like to find a matching between $x$ and $y$ such that

$($a$)($no missing$)$ every $x[i]$ is matched to at least one $y[j],$ and every $y[j]$ is matched to at least one $x[i]$;

$($b$)($no crossing$)$ if for $i_1{i}_2,x[i_1]$ matches with $y[j_1]$ and $x[i_2]$ matches with $y[j_2],$ we must have $j_1{j}_2.$

Your job is to design an $O(n^2)-$time algorithm to find a matching such that the sum of $|x[i]-y[j]|$ for all matched pairs $(x[i],y[j])$ is minimized. The figure below shows an optimal matching between two given sequences, which yields a sum of $2.$ Your algorithm only needs to return the minimum sum; the actual matching is not required.

My own solution is converting the relationship into a $2$D map with each cell $[$i$][$j$]$ meaning the abs difference of x$[$i$]$ and y$[$j$],$ then find the solution using minimum cost path finding methods$($dynamic programming for minimum cost path finding cost O$($n$^2)).$

well clearly the current solution on this chegg website is incorrect as it first didnt adress how ii and iii is performed and how it avoid crossing$($requirement $2)$ issue.