Sponsored
Sponsored
This approach relies on sorting both the seats and students arrays. After sorting them, we pair the i-th seat with the i-th student. The sum of absolute differences between corresponding elements gives us the minimum number of moves required.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) since sorting is in-place.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5int minMovesToSeat(std::vector<int>& seats, std::vector<int>& students) {
6 std::sort(seats.begin(), seats.end());
7 std::sort(students.begin(), students.end());
8 int result = 0;
9 for (size_t i = 0; i < seats.size(); ++i) {
10 result += std::abs(seats[i] - students[i]);
11 }
12 return result;
13}
14
15int main() {
16 std::vector<int> seats = {3, 1, 5};
17 std::vector<int> students = {2, 7, 4};
18 std::cout << minMovesToSeat(seats, students) << std::endl;
19 return 0;
20}Both vectors are sorted using std::sort. We compute the total of absolute differences between corresponding elements in the sorted arrays to find the minimum number of moves.
This approach involves creating frequency arrays or maps for both seats and students positions. Align students to seats by finding the closest available seat iteratively, simulating a greedy approach.
Time Complexity: O(n + m), where m is the range of possible positions (maximum 100).
Space Complexity: O(m) due to frequency arrays.
1
Establish frequency accounts for seats and students. Traverse each array hyper-sequentially to compute corresponding minimal moves using a pairwise greedy matching algorithm.