algoadvance

Leetcode 2037. Minimum Number of Moves to Seat Everyone

Problem Statement

You are given two arrays seats and students of equal length, where seats[i] represents the position of the ith seat and students[i] represents the starting position of the ith student. Each student can move to an adjacent seat by moving to seats[i] + 1 or seats[i] - 1.

Return the minimum number of moves required to seat all the students such that each student gets a seat.

Clarifying Questions

1. Are the positions in the seats and students arrays guaranteed to be distinct?
   • Yes, for simplicity, assume all positions in seats and students are distinct.
2. Is the range of positions in seats and students arbitrary?
   • Yes, they can be any integer values.
3. Should students always occupy the nearest seats optimally?
   • Yes, the goal is to minimize the total number of moves, so students should be assigned seats in a way that minimizes the sum of the distances they move.
4. Are negative positions allowed in the seats and students arrays?
   • Yes, positions can be negative or positive integers.

Strategy

To achieve the minimum number of moves:

• Sort both the seats and students arrays.
• Pair each student with the corresponding seat in the sorted order.
• Calculate the distance from each student to their respective seat and sum these distances.

This approach works because sorting both arrays ensures that each student is paired with the closest unoccupied seat, minimizing the overall distance.

Time Complexity

• Sorting the seats and students arrays takes (O(n \log n)), where (n) is the number of students/seats.
• Calculating the total distance row by row takes (O(n)).
• Hence, the overall time complexity is (O(n \log n)).

Code

Here is the C++ implementation representing the strategy described.

#include <iostream>
#include <vector>
#include <algorithm>

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

int main() {
    Solution solution;
    std::vector<int> seats = {3, 1, 5};
    std::vector<int> students = {2, 7, 4};
    std::cout << "Minimum number of moves: " << solution.minMovesToSeat(seats, students) << std::endl;
    return 0;
}

This code:

1. Sorts the seats and students arrays.
2. Computes the sum of absolute differences between corresponding elements in the sorted arrays.
3. Returns the total number of moves required to seat all students optimally.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?