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 <stdio.h>
2#include <stdlib.h>
3
4int cmpfunc(const void * a, const void * b) {
5 return (*(int*)a - *(int*)b);
6}
7
8int minMovesToSeat(int* seats, int seatsSize, int* students, int studentsSize) {
9 qsort(seats, seatsSize, sizeof(int), cmpfunc);
10 qsort(students, studentsSize, sizeof(int), cmpfunc);
11 int result = 0;
12 for (int i = 0; i < seatsSize; i++) {
13 result += abs(seats[i] - students[i]);
14 }
15 return result;
16}
17
18int main() {
19 int seats[] = {3,1,5};
20 int students[] = {2,7,4};
21 int n = sizeof(seats)/sizeof(seats[0]);
22 printf("%d\n", minMovesToSeat(seats, n, students, n));
23 return 0;
24}We define a comparison function cmpfunc for sorting. Using qsort, both arrays are sorted. The absolute differences between paired elements from sorted arrays are summed to get the minimum 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
class Solution {
public int MinMovesToSeat(int[] seats, int[] students) {
int[] seatCount = new int[101];
int[] studentCount = new int[101];
foreach (int seat in seats) seatCount[seat]++;
foreach (int student in students) studentCount[student]++;
int i = 0, j = 0, moves = 0;
while (i < 101 && j < 101) {
if (seatCount[i] > 0 && studentCount[j] > 0) {
int minCount = Math.Min(seatCount[i], studentCount[j]);
moves += Math.Abs(i - j) * minCount;
seatCount[i] -= minCount;
studentCount[j] -= minCount;
}
if (seatCount[i] == 0) i++;
if (studentCount[j] == 0) j++;
}
return moves;
}
static void Main(string[] args) {
Solution sol = new Solution();
int[] seats = {3, 1, 5};
int[] students = {2, 7, 4};
Console.WriteLine(sol.MinMovesToSeat(seats, students));
}
}Define seat and student position counts using integer arrays. Traverse with parallel iterators, reallocating students to minimize moves based on minimum position variance.