# greedy algorithms – Find the maximum number of valid cartesian coordinates

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?