[Leetcode/Array, Greedy, Sorting] 2037. Minimum Number of Moves to Seat Everyone

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        students.sort(reverse=True)
        seats.sort(reverse=True)

        minMove = 0
        for i in range(len(students)):
            minMove += abs(students[i] - seats[i])
        return minMove

✅ Why Use abs() (Absolute Value)?

The problem asks for the total number of moves to align each student with a seat.

Each move increases or decreases a student's position by 1 unit, so the number of moves between:

• a student at position 3
• and a seat at position 7

...is 4 (7 - 3 = 4).

But if the student is at position 7 and the seat is at 3, then:

• 3 - 7 = -4, but moves can't be negative.
• So we take abs(3 - 7) → 4 moves.

❓ Why does the minMove we calculate using abs(seats[i] - students[i]) actually give the minimum total number of moves?

✅ Because we're using a greedy strategy with sorting.

Step-by-step logic:

1. Sort both seats and students arrays.
   • We pair the smallest available seat with the smallest-positioned student,
   • the second smallest seat with the second smallest student,
   • and so on...
2. Example

seats = [1, 3, 7]
students = [2, 6, 5]

# Sorted:
seats = [1, 3, 7]
students = [2, 5, 6]

# Matching:
abs(1 - 2) = 1
abs(3 - 5) = 2
abs(7 - 6) = 1
Total = 4 moves (minimum)