Minimize the number of moves required to seat each passenger in a chair
You are a bus conductor with n chairs and n passengers. Given the array chairs[] and passengers[] representing their initial positions, your goal is to minimize the number of moves required to seat each passenger in a chair, ensuring that no two passengers occupy the same chair. You can move a passenger by increasing or decreasing their position by 1. Find the minimum number of moves needed to achieve the desired seating arrangement, considering any initial overlapping positions.
Examples:
Input: chairs = [3, 1, 5], passengers = [2, 7, 4]
Output: 4
Explanation:
- The first passenger is moved from position 2 to position 1
- The second passenger is moved from position 7 to position 5
- The third passenger is moved from position 4 to position 3
- Total moves: 1+2+1 = 4
Input: chairs = [2, 2, 6, 6], passengers = [1, 3, 2, 6]
Output: 4
Explanation:
- The first passenger is moved from position 1 to position 2
- The second passenger is moved from position 3 to position 6
- The third passenger is not moved
- The fourth passenger is not moved
- Total moves: 1+3+0+0 = 4
Approach: To solve the problem follow the below idea:
- The given problem can be solved efficiently using sorting.
- The number of moves can be calculated by taking the absolute of chairs[i] – passengers[i], where 0 < i < length of the array(n).
Below is the implementation of the above approach:
C++
// C++ implementation for the // above approach #include <bits/stdc++.h> using namespace std; int findMoves(vector< int >& chairs, vector< int >& passengers, int n) { // Sorting both the arrays sort(chairs.begin(), chairs.end()); sort(passengers.begin(), passengers.end()); int ans = 0; // Calculating minimum // position changed for ( int i = 0; i < n; i++) { ans += abs (chairs[i] - passengers[i]); } return ans; } // Driver code int main() { vector< int > chairs = { 3, 1, 5 }; vector< int > passengers = { 2, 7, 4 }; int n = 3; // Function call cout << findMoves(chairs, passengers, n); return 0; } |
Java
// Java implementation for // the above code import java.util.*; class GFG { static int findMoves( int [] chairs, int [] passengers, int n) { // Sorting both the arrays Arrays.sort(chairs); Arrays.sort(passengers); int ans = 0 ; // Calculating minimum // position changed for ( int i = 0 ; i < n; i++) { ans += Math.abs(chairs[i] - passengers[i]); } return ans; } // Driver code public static void main(String[] args) { int [] chairs = { 3 , 1 , 5 }; int [] passengers = { 2 , 7 , 4 }; int n = 3 ; // Function call System.out.print(findMoves(chairs, passengers, n)); } } |
Python3
# Python implementation for # the above approach def findMoves(chairs, passengers, n): # sorting both the arrays chairs.sort() passengers.sort() ans = 0 # calculating minimum # position changed for i in range (n): ans + = abs (chairs[i] - passengers[i]) return ans # Driver code chairs = [ 3 , 1 , 5 ] passengers = [ 2 , 7 , 4 ] n = 3 # Function call print (findMoves(chairs, passengers, n)) |
C#
// C# implementation for the // above approach using System; using System.Collections.Generic; public class GFG { // Function to find the minimum number of moves required static int FindMoves(List< int > chairs, List< int > passengers, int n) { // Sorting both the lists chairs.Sort(); passengers.Sort(); int ans = 0; // Calculating the minimum position changed for ( int i = 0; i < n; i++) { ans += Math.Abs(chairs[i] - passengers[i]); } return ans; } // Driver code public static void Main() { List< int > chairs = new List< int >{ 3, 1, 5 }; List< int > passengers = new List< int >{ 2, 7, 4 }; int n = 3; // Function call Console.WriteLine(FindMoves(chairs, passengers, n)); } } // This code is contributed by Susobhan Akhuli |
Javascript
function findMoves(chairs, passengers, n) { chairs.sort((a, b) => a - b); passengers.sort((a, b) => a - b); let ans = 0; for (let i = 0; i < n; i++) { ans += Math.abs(chairs[i] - passengers[i]); } return ans; } // Nikunj Sonigara let chairs = [3, 1, 5]; let passengers = [2, 7, 4]; let n = 3; console.log(findMoves(chairs, passengers, n)); |
4
Time Complexity: O(n*log n), n is the length of the array
Auxiliary Space: O(1)
Contact Us