Minimum Number of Moves to Seat Everyone

Problem Description

There are n available seats and n students standing in a room. You are given an array seats of length n, where seats[i] is the position of the i-th seat. You are also given the array students of length n, where students[j] is the position of the j-th student. You may perform the following move any number of times: Increase or decrease the position of the i-th student by 1 (i.e., moving the i-th student from position x to x + 1 or x - 1). Return the minimum number of moves required to move each student to a seat such that no two students are in the same seat. Note that there may be multiple seats or students in the same position at the beginning.

Key Insights

• Sorting both the seats and students arrays allows for a direct comparison of positions.
• The optimal way to minimize the total moves is to pair the closest student to the closest seat after sorting.
• The total moves can be calculated as the sum of the absolute differences between the paired seats and students.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the arrays.
Space Complexity: O(1) for the calculations, excluding the input space.

Solution

To solve the problem, we can follow these steps:

1. Sort both the seats and students arrays.
2. Initialize a variable to keep track of the total number of moves.
3. Iterate through both sorted arrays simultaneously, calculating the absolute difference between each corresponding pair and adding this to the total moves.
4. Return the total number of moves.

The algorithm relies on sorting to ensure that each student is matched to the nearest available seat, which minimizes the total movement required.

Code Solutions