Minimize the moves required to seat each passenger in a chair

Given two arrays chairs[] and passengers[] of equal length, where chairs[i] is the position of the i^th chair and passengers[j] is the position of the j^th passenger. Perform the following move any number of times:

• Increase or decrease the position of the i^th passenger by 1 (i.e., moving the i^th passenger from position x to x+1 or x-1)

Return the minimum number of moves required to move each passenger to get a chair such that no two passengers are in the same chair and every passenger gets a chair.
Note: Initially, multiple passengers or chairs may occupy the same position.

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] Using Sorting - O(n log n) Time and O(1) Space

The main idea is to solve the problem by first sorting both the chairs and passengers arrays. This ensures that each passenger is matched with the closest available chair in a one-to-one manner. After sorting, the number of moves for each passenger is calculated using the absolute difference between their position and the corresponding chair’s position. Summing up these values for all elements gives the minimum total number of moves required.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findMoves(vector<int>& chairs, vector<int>& passengers){

    // Sorting both the arrays
    sort(chairs.begin(), chairs.end());
    sort(passengers.begin(), passengers.end());
    
    int ans = 0;
    int n = chairs.size();
    
    // Calculating minimum
    // position changed
    for (int i = 0; i < n; i++) {
        ans += abs(chairs[i] - passengers[i]);
    }
    
    return ans;
}

int main(){
    
    vector<int> chairs = {3, 1, 5};
    vector<int> passengers = {2, 7, 4};
    
    cout << findMoves(chairs, passengers);
    return 0;
}

import java.util.Arrays;

class GFG {

    static int findMoves(int[] chairs, int[] passengers){

        // Sorting both the arrays
        Arrays.sort(chairs) ;
        Arrays.sort(passengers) ;
        
        int ans = 0 ;
        int n = chairs.length;
        
        // Calculating minimum
        // position changed
        for (int i = 0 ; i < n ; i++) {
            ans += Math.abs(chairs[i] - passengers[i]) ;
        }
        
        return ans ;
    }

    public static void main(String[] args)
    {
        int[] chairs = {3, 1, 5};
        int[] passengers = {2, 7, 4};
        
        System.out.print(findMoves(chairs, passengers));
    }
}

def findMoves(chairs, passengers):
    # sorting both the arrays
    chairs.sort()
    passengers.sort()
    
    ans = 0
    n = len(chairs)
    
    # calculating minimum position changes
    for i in range(n):
        ans += abs(chairs[i] - passengers[i])
        
    return ans


if __name__ == "__main__":
    chairs = [3, 1, 5]
    passengers = [2, 7, 4]
    print(findMoves(chairs, passengers))

using System;

public class GfG {
    // Function to find the minimum number of moves required
    static int findMoves(int[] chairs, int[] passengers){
        
        // Sorting both arrays
        Array.Sort(chairs);
        Array.Sort(passengers);

        int ans = 0;
        int n = chairs.Length;

        // Calculating the minimum position changed
        for (int i = 0; i < n; i++) {
            ans += Math.Abs(chairs[i] - passengers[i]);
        }

        return ans;
    }

    public static void Main(){
        
        int[] chairs = { 3, 1, 5 };
        int[] passengers = { 2, 7, 4 };
        
        Console.WriteLine(findMoves(chairs, passengers));
    }
}

function findMoves(chairs, passengers) {
    
  chairs.sort((a, b) => a - b);
  passengers.sort((a, b) => a - b);
  
  let ans = 0 ;
  let n = chairs.length;
  
  for (let i = 0; i < n; i++) {
    ans += Math.abs(chairs[i] - passengers[i]);
  }
  return ans;
}

// Driver Code
let chairs = [3, 1, 5];
let passengers = [2, 7, 4];
console.log(findMoves(chairs, passengers));

4