#2037

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Number of Moves to Seat Everyone

Calculate the minimum total moves to seat each student using greedy assignment and invariant validation efficiently.

Problem Statement

You are given two arrays of length n: seats and students, representing the positions of n seats and n students in a room. Each student must occupy one seat, and multiple students cannot occupy the same seat.

In one move, a student can shift to an adjacent position by 1 unit. Return the minimum total moves needed to seat every student following the rule that no two students share a seat.

Examples

Example 1

Input: seats = [3,1,5], students = [2,7,4]

Output: 4

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

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

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 Approach

Sort and Pair

Sort the seats and students arrays in ascending order. Pair each student with the corresponding seat by index to ensure minimal distance travel and optimal greedy assignment.

Calculate Moves

Iterate through the paired arrays and compute the absolute difference between each student position and their assigned seat. Sum these differences to get the total minimum moves.

Validate Greedy Choice

Ensure that no seat is assigned to multiple students after sorting. The invariant of one-to-one mapping between sorted arrays guarantees correctness, preventing overlap or unnecessary moves.

Complexity Analysis

Metric	Value
Time	O(n + m)
Space	O(m)

Sorting takes O(n log n) and iterating to sum moves takes O(n), giving O(n log n) overall. Space is O(1) beyond input arrays since pairing is done in-place or with simple iteration.

What Interviewers Usually Probe

The interviewer expects recognition of greedy assignment as the core pattern.
They may hint at sorting both arrays to minimize distance without explicitly saying it.
Look for opportunities to validate that no two students share a seat after pairing.

Common Pitfalls or Variants

Common pitfalls

Forgetting to sort both arrays leads to suboptimal total moves.
Assigning students without checking one-to-one mapping can cause seat collisions.
Counting moves incorrectly by using differences without absolute value produces wrong totals.

Follow-up variants

Allowing multiple students per seat, requiring conflict resolution logic.
Seats and students may have different lengths, necessitating extra handling.
Introducing negative positions or larger ranges, requiring careful indexing or adjusted calculations.

FAQ

What is the minimum number of moves to seat everyone problem about?

It asks for moving each student to a seat with the least total moves using greedy assignment and absolute position differences.

How does the greedy choice pattern apply here?

Sorting both arrays ensures each student goes to the nearest available seat, minimizing total moves and validating invariants.

Can students occupy the same seat in this problem?

No, each seat must be occupied by exactly one student, and the algorithm must enforce this constraint.

What is the expected time complexity?

Sorting both arrays takes O(n log n) and summing moves takes O(n), resulting in O(n log n) overall.

Is sorting necessary for the solution?

Yes, sorting is critical to the greedy choice and invariant validation that ensures minimal total moves.

terminal

Solution

Solution 1: Sorting

Sort both arrays, then traverse the two arrays, calculate the distance between each student's seat and their actual seat, and add all the distances to get the answer.

1

2

3

4

5

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        seats.sort()
        students.sort()
        return sum(abs(a - b) for a, b in zip(seats, students))

Continue Practicing

#1833 maximum ice cream bars #2007 find original array from doubled array #2071 maximum number of tasks you can assign