Formación de pares tal que la suma máxima de pares se minimice

Dada una array de tamaño 2 * N enteros. Divida la array en N pares, de modo que se minimice la suma máxima de pares. En otras palabras, la división óptima de la array en N pares debería dar como resultado una suma máxima de pares que es el mínimo de otra suma máxima de pares de todas las posibilidades.
Ejemplos: 
 

Entrada: N = 2 
arr[] = { 5, 8, 3, 9 } 
Salida: (3, 9) (5, 8) 
Explicación: 
Los pares posibles son: 
1. (8, 9) (3, 5) Suma máxima de un par = 17 
2. (5, 9) (3, 8) Suma máxima de un par = 14 
3. (3, 9) (5, 8) Suma máxima de un par = 13 
Así, en el caso 3, la la suma máxima del par es la mínima de todos los demás casos. Por lo tanto, la respuesta es (3, 9) (5, 8).
Entrada: N = 2 
arr[] = { 9, 6, 5, 1 } 
Salida: (1, 9) (5, 6) 
 

Enfoque: la idea es ordenar primero la array dada y luego iterar sobre el ciclo para formar pares (i, j) donde yo comenzaría desde 0 y j comenzaría desde el final de la array correspondientemente. Incrementa i y Decrementa j para formar el siguiente par y así sucesivamente.
A continuación se muestra la implementación del enfoque anterior. 
 

// CPP Program to divide the array into
// N pairs such that maximum pair is minimized
#include <bits/stdc++.h>
 
using namespace std;
 
void findOptimalPairs(int arr[], int N)
{
    sort(arr, arr + N);
 
    // After Sorting Maintain two variables i and j
    // pointing to start and end of array Such that
    // smallest element of array pairs with largest
    // element
    for (int i = 0, j = N - 1; i <= j; i++, j--)
        cout << "(" << arr[i] << ", " << arr[j] << ")" << " ";
}
 
// Driver Code
int main()
{
    int arr[] = { 9, 6, 5, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    findOptimalPairs(arr, N);
    return 0;
}

// Java Program to divide the array into
// N pairs such that maximum pair is minimized
import java.io.*;
import java.util.Arrays;
 
class GFG {
     
static void findOptimalPairs(int arr[], int N)
{
    Arrays.sort(arr);
 
    // After Sorting Maintain two variables i and j
    // pointing to start and end of array Such that
    // smallest element of array pairs with largest
    // element
    for (int i = 0, j = N - 1; i <= j; i++, j--)
        System.out.print( "(" + arr[i] + ", " + arr[j] + ")" + " ");
}
 
    // Driver Code
    public static void main (String[] args)
    {
        int arr[] = {9, 6, 5, 1};
        int N = arr.length;
 
        findOptimalPairs(arr, N);
    }
}
 
// This code is contributed by anuj_67.

# Python 3 Program to divide the array into
# N pairs such that maximum pair is minimized
 
def findOptimalPairs(arr, N):
    arr.sort(reverse = False)
 
    # After Sorting Maintain two variables
    # i and j pointing to start and end of
    # array Such that smallest element of
    # array pairs with largest element
    i = 0
    j = N - 1
    while(i <= j):
        print("(", arr[i], ",",
                   arr[j], ")", end = " ")
        i += 1
        j -= 1
 
# Driver Code
if __name__ == '__main__':
    arr = [9, 6, 5, 1]
    N = len(arr)
 
    findOptimalPairs(arr, N)
     
# This code is contributed by
# Sahil_Shelangia

// C# Program to divide the array into
// N pairs such that maximum pair is minimized
 
using System;
 
public class GFG{
    static void findOptimalPairs(int []arr, int N)
{
    Array.Sort(arr);
 
    // After Sorting Maintain two variables i and j
    // pointing to start and end of array Such that
    // smallest element of array pairs with largest
    // element
    for (int i = 0, j = N - 1; i <= j; i++, j--)
        Console.Write( "(" + arr[i] + ", " + arr[j] + ")" + " ");
}
 
    // Driver Code
    static public void Main (){
         
        int []arr = {9, 6, 5, 1};
        int N = arr.Length;
        findOptimalPairs(arr, N);
 
 
// This code is contributed by ajit.
 
    }
}

<?php
// PHP Program to divide the array into
// N pairs such that maximum pair is minimized
 
function findOptimalPairs($arr, $N)
{
    sort($arr);
 
    // After Sorting Maintain two variables
    // i and j pointing to start and end of
    // array Such that smallest element of
    // array pairs with largest element
    for ($i = 0, $j = $N - 1; $i <= $j; $i++, $j--)
            echo "(", $arr[$i],
                 ", ", $arr[$j], ")", " ";
}
 
// Driver Code
$arr = array( 9, 6, 5, 1 );
$N = sizeof($arr);
 
findOptimalPairs($arr, $N);
 
// This code is contributed by jit_t
?>

<script>
 
/// Javascript Program to divide the array into
// N pairs such that maximum pair is minimized
function findOptimalPairs(arr, N)
{
    arr.sort(function(a,b){ return a-b;});
 
    // After Sorting Maintain two variables i and j
    // pointing to start and end of array Such that
    // smallest element of array pairs with largest
    // element
    for (var i = 0, j = N - 1; i <= j; i++, j--)
        document.write("(" + arr[i] + ", " + arr[j] + ")" + " ");
}
 
// Driver Code
var arr = [ 9, 6, 5, 1 ];
var N = arr.length;
findOptimalPairs(arr, N);
 
</script>

(1, 9) (5, 6)

Complejidad de tiempo: O(n*log n) donde n es el tamaño de la array.
Espacio Auxiliar: O(1)