Given a 2D array rooks of length n, where rooks[i] = [xi, yi] indicates the position of a rook on an n x n chess board. Your task is to move the rooks 1 cell at a time vertically or horizontally (to an adjacent cell) such that the board becomes peaceful.
A board is peaceful if there is exactly one rook in each row and each column.
Return the minimum number of moves required to get a peaceful board.
Note that at no point can there be two rooks in the same cell.
Example 1:
Input:rooks = [[0,0],[1,0],[1,1]]
Output:3
Explanation:
Example 2:
Input:rooks = [[0,0],[0,1],[0,2],[0,3]]
Output:6
Explanation:
Constraints:
1 <= n == rooks.length <= 500
0 <= xi, yi <= n - 1
The input is generated such that there are no 2 rooks in the same cell.
Solutions
Solution 1: Greedy Algorithm
We can sort all the cars by their x-coordinates, and then allocate the cars to each row in order, calculating the sum of distances from each car to its target position. Then, sort all the cars by their y-coordinates and use the same method to calculate the sum of distances from each car to its target position. Finally, the sum of these two distances is the answer.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the number of cars.