Minimum Number of Moves to Seat Everyone

easy array sorting

Problem

There are n seats and n students. You are given two arrays seats and students of length n where seats[i] is the position of the i-th seat and students[j] is the position of the j-th student. You may move any student by 1 unit at a time. Return the minimum number of moves required so that every student is in a distinct seat.

Inputseats = [3, 1, 5], students = [2, 7, 4]

Output4

Sort to seats=[1,3,5], students=[2,4,7]. Diffs |1−2|+|3−4|+|5−7| = 1+1+2 = 4.

seats (comma-separated)

students (comma-separated)

def min_moves_to_seat(seats, students):
    seats.sort()
    students.sort()
    total = 0
    for i in range(len(seats)):
        total += abs(seats[i] - students[i])
    return total

function minMovesToSeat(seats, students) {
  seats.sort((a, b) => a - b);
  students.sort((a, b) => a - b);
  let total = 0;
  for (let i = 0; i < seats.length; i++) {
    total += Math.abs(seats[i] - students[i]);
  }
  return total;
}

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

int minMovesToSeat(vector<int>& seats, vector<int>& students) {
    sort(seats.begin(), seats.end());
    sort(students.begin(), students.end());
    int total = 0;
    for (int i = 0; i < (int)seats.size(); i++) {
        total += abs(seats[i] - students[i]);
    }
    return total;
}

Explanation

The cost of seating a student is the distance they walk, and the total moves we want to minimize is the sum of those distances. The neat result is that the best pairing is simply: send the closest student to the closest seat — match them in sorted order.

So we sort both arrays, then pair seats[i] with students[i] at the same index and add up abs(seats[i] - students[i]).

Why does sorted matching win? If you ever crossed two pairs (a near student going to a far seat), un-crossing them never increases the total distance. So the sorted, non-crossing matching is always optimal.

Example: seats=[3,1,5], students=[2,7,4]. Sorted they are [1,3,5] and [2,4,7]. The distances are |1-2|=1, |3-4|=1, |5-7|=2.

Summing gives 1 + 1 + 2 = 4 moves. Two sorts and one pass do the whole job.

Time: O(n log n) Space: O(1)