The Minimum Number of Moves to Seat Everyone coding problem is a straightforward but essential challenge often used to introduce greedy optimization. You are given two arrays: seats and students. Each element in the arrays represents a position on a 1D line. You need to move each student to a seat such that no two students occupy the same seat, and the total distance moved by all students is minimized.
This question is a favorite for entry-level positions at companies like Microsoft, Amazon, and Google. It tests if a candidate understands the "assignment problem" in its simplest form. The interviewer wants to see if you can recognize that the optimal strategy is to pair the -th smallest student position with the -th smallest seat position.
This problem follows the Array, Sorting, Counting Sort, Greedy interview pattern. The greedy insight is that sorting both arrays ensures that each student is moved to the "closest" available seat in a global sense. If you sort both seats and students, the total distance is simply the sum of abs(seats[i] - students[i]). While standard sorting (O(n log n)) is common, if the range of positions is small, Counting Sort (O(n)) can also be used.
Seats: [3, 1, 5] Students: [2, 7, 4]
The most common mistake is over-thinking the movement and trying to use a complex matching algorithm. Another error is failing to sort the arrays, which leads to a completely incorrect (and usually larger) result. Some candidates might also forget to use the absolute value when calculating the distance between a student and a seat.
For "Easy" array problems, always ask yourself: "Does sorting the data make the greedy choice obvious?". Sorting is one of the most powerful pre-processing steps in interview coding and should be in your immediate toolkit for any optimization task.
