Question

2037. Minimum Number of Moves to Seat Everyone

中文文档

Description

There are n seats and n students 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 from position 2 to position 1 using 1 move.
- The second student is moved from from position 7 to position 5 using 2 moves.
- The third student is moved from 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 from position 3 to position 4 using 1 move.
- The third student is moved from from position 2 to position 5 using 3 moves.
- The fourth student is moved from 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 from position 1 to position 2 using 1 move.
- The second student is moved from 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

Solutions

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.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the length of the arrays seats and students.

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))

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

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

func minMovesToSeat(seats []int, students []int) (ans int) {
  sort.Ints(seats)
  sort.Ints(students)
  for i, a := range seats {
    b := students[i]
    ans += abs(a - b)
  }
  return
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}

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

impl Solution {
  pub fn min_moves_to_seat(mut seats: Vec<i32>, mut students: Vec<i32>) -> i32 {
    seats.sort();
    students.sort();
    let n = seats.len();
    let mut ans = 0;
    for i in 0..n {
      ans += (seats[i] - students[i]).abs();
    }
    ans
  }
}

int cmp(const void* a, const void* b) {
  return *(int*) a - *(int*) b;
}

int minMovesToSeat(int* seats, int seatsSize, int* students, int studentsSize) {
  qsort(seats, seatsSize, sizeof(int), cmp);
  qsort(students, studentsSize, sizeof(int), cmp);
  int ans = 0;
  for (int i = 0; i < seatsSize; i++) {
    ans += abs(seats[i] - students[i]);
  }
  return ans;
}