Minimum Number of Moves to Seat Everyone — LeetCode 2037 Python Solution

The problem

There are n availabe seats and n students standing in a room. You are given an array seats of length n, where seats[i] is the position of the ith seat.

Example

Input

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

Output

4

Explanation

The students are moved as follows:

Python solution

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

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2037. Minimum Number of Moves to Seat Everyone is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems