{x}
blog image

Minimum Number of Moves to Seat Everyone

There are n availabe 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 ith seat. You are also given the array students of length n, where students[j] is the position of the jth student.

You may perform the following move any number of times:

  • Increase or decrease the position of the ith student by 1 (i.e., moving the ith 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.

 

Example 1:

Input: seats = [3,1,5], students = [2,7,4]
Output: 4
Explanation: The students are moved as follows:
- The first student is moved from position 2 to position 1 using 1 move.
- The second student is moved from position 7 to position 5 using 2 moves.
- The third student is moved from position 4 to position 3 using 1 move.
In total, 1 + 2 + 1 = 4 moves were used.

Example 2:

Input: seats = [4,1,5,9], students = [1,3,2,6]
Output: 7
Explanation: The students are moved as follows:
- The first student is not moved.
- The second student is moved from position 3 to position 4 using 1 move.
- The third student is moved from position 2 to position 5 using 3 moves.
- The fourth student is moved from position 6 to position 9 using 3 moves.
In total, 0 + 1 + 3 + 3 = 7 moves were used.

Example 3:

Input: seats = [2,2,6,6], students = [1,3,2,6]
Output: 4
Explanation: Note that there are two seats at position 2 and two seats at position 6.
The students are moved as follows:
- The first student is moved from position 1 to position 2 using 1 move.
- The second student is moved from position 3 to position 6 using 3 moves.
- The third student is not moved.
- The fourth student is not moved.
In total, 1 + 3 + 0 + 0 = 4 moves were used.

 

Constraints:

  • n == seats.length == students.length
  • 1 <= n <= 100
  • 1 <= seats[i], students[j] <= 100

Solution Explanation: Minimum Number of Moves to Seat Everyone

This problem asks for the minimum number of moves required to seat n students in n seats, where each move involves shifting a student's position by 1. The optimal solution leverages the power of sorting.

Approach:

The core idea is that to minimize the total moves, we should match students and seats in a way that minimizes the distance between each student's initial position and their assigned seat. The most efficient way to achieve this is to sort both the seats and students arrays. After sorting, the i-th element in the seats array can be optimally paired with the i-th element in the students array. The total number of moves is then simply the sum of the absolute differences between corresponding elements in the sorted arrays.

Time Complexity Analysis:

The dominant operations are the sorting of the seats and students arrays. Most efficient sorting algorithms (like merge sort or quicksort) have a time complexity of O(n log n), where n is the number of students (and seats). The subsequent calculation of the sum of absolute differences takes linear time, O(n). Therefore, the overall time complexity is O(n log n), dominated by the sorting step.

Space Complexity Analysis:

In-place sorting algorithms can be used, which modify the input arrays directly without requiring significant extra space. The space complexity is therefore O(log n), due to the space used by the recursive calls in some sorting algorithms, or potentially O(1) with an in-place sort like Heapsort.

Code Implementation (Python):

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        seats.sort()
        students.sort()
        total_moves = 0
        for i in range(len(seats)):
            total_moves += abs(seats[i] - students[i])
        return total_moves

Code Implementation (Java):

import java.util.Arrays;
 
class Solution {
    public int minMovesToSeat(int[] seats, int[] students) {
        Arrays.sort(seats);
        Arrays.sort(students);
        int totalMoves = 0;
        for (int i = 0; i < seats.length; i++) {
            totalMoves += Math.abs(seats[i] - students[i]);
        }
        return totalMoves;
    }
}

Code Implementation (C++):

#include <algorithm>
#include <vector>
#include <cmath>
 
class Solution {
public:
    int minMovesToSeat(std::vector<int>& seats, std::vector<int>& students) {
        std::sort(seats.begin(), seats.end());
        std::sort(students.begin(), students.end());
        int totalMoves = 0;
        for (size_t i = 0; i < seats.size(); ++i) {
            totalMoves += std::abs(seats[i] - students[i]);
        }
        return totalMoves;
    }
};

The code in other languages (Go, TypeScript, Rust, C) follows a similar structure, adapting the sorting and absolute difference calculation to the specific language syntax. The core algorithm remains the same, offering an efficient solution to the problem.