Given a list X containing m number of x coordinates and a list Y containing m number of y coordinates. The coordinate (x, y) is valid if and only if the difference between x and y is less than or equal to d. I need to find out the maximum number of valid coordinates. Here is my algorithm.
sort the list X in non-decreasing order sort the list Y in non-decreasing order for x in X: for y in Y: if abs(x - y) <= d: let x match with y remove x from X remove y from Y
Can this algorithm give me maximum number of valid pairs? If yes, is there any more efficient algorithm? The nested loop means the worst-case time is $ O(m^2)$ . Is there any log linear time $ O(mlogm)$ algorithm for this question?