💬 Discord
Sign In
NeetCode #764LC-2037EasyGreedy
← Back to All Problems

#764 · #2037 · Minimum Number of Moves to Seat Everyone(使每位学生都有座位的最少移动次数)

📌 Problem Statement & Constraints

There are n seats and n students. seats[i] is the position of the i-th seat and students[j] the position of the j-th student. Each move shifts one student by one position. Return the minimum number of moves so that no two students share a seat. Constraints: 1 <= n <= 100, 1 <= seats[i], students[i] <= 100.

💡 Core Algorithmic Approaches

  1. Sort both arrays so that the i-th smallest student is matched with the i-th smallest seat.
  2. The cost of a matching is the sum of absolute differences.
  3. The sorted matching is optimal by an exchange argument: swapping any crossing assignment cannot increase the total distance.
  4. Sum the absolute differences over the sorted pairs.

💻 Benchmark Python3 Implementation

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the two sorts dominate.
💾 Space Complexity
O(1) beyond the sorts.

⚠️ Interview Pitfalls & Follow-ups

  • Not sorting: matching in the given order can be far from optimal.
  • Matching each student to the nearest free seat greedily: that is not always globally optimal; the sorted matching is.
  • Summing signed differences: moves are counts of positions, so the absolute value is required.
  • Assuming seats and students must be distinct positions: the constraints allow duplicates; only the final assignment must be a bijection.