Minimum Number Of Moves To Seat Everyone - Leetcode Solution

Problem Description:

There are n seats and n students in a classroom. 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:

1. Increase or decrease the position of the ith student by 1.

You must perform the moves in such a way that every student is seated in a seat. Return the minimum number of moves required to seat all the students.

It is guaranteed that there is at least one valid configuration of the seats that can be achieved by performing the moves.

Solution:

1. Sort both the arrays, seats and students, in increasing order.
2. Initialize a variable, moves, to 0, which will keep track of the number of moves required to seat all the students.
3. Iterate over the students array and for each student, find the nearest seat that is available and assign it to the student.
4. If there is no available seat on the left of the student's current position, move the student to the right.
5. If there is no available seat on the right of the student's current position, move the student to the left.
6. If there is an available seat on both sides, calculate the distance to the seat on the left and the distance to the seat on the right and move the student to the seat that is closer.
7. After assigning a seat to a student, mark that seat as unavailable.
8. Repeat steps 3-7 until all students have been assigned a seat.
9. Return the value of moves, which represents the minimum number of moves required to seat all the students.

Code:

class Solution:
    def minMovesToSeat(self, seats: List[int], students: List[int]) -> int:
        
        # sort both arrays in increasing order
        seats.sort()
        students.sort()
        
        moves = 0
        n = len(seats)
        
        for i in range(n):
            # find the nearest available seat
            if seats[i] < students[i]:
                while i < n and seats[i] < students[i]:
                    i += 1
                if i == n:
                    moves += students[i-1] - seats[i-1]
                else:
                    moves += seats[i] - students[i]
            else:
                while i < n and seats[i] > students[i]:
                    i += 1
                if i == n:
                    moves += seats[i-1] - students[i-1]
                else:
                    moves += students[i] - seats[i]

        return moves

Time Complexity: O(nlogn) (sorting) + O(n) (loop) = O(nlogn)

Space Complexity: O(1)

1