Pair formation such that maximum pair sum is minimized

Given an array arr[] of 2N integers, where N is any positive integer. The task is to divide the array into N pairs such that the pair sum minimizes the maximum sum of a pair i.e., the pair sums for this partition are minimum of the maximum pair sum of all possible partitions of the array.

Examples:

Input : arr[] = {6, 9, 4, 10}
Output : (4,10)(6,9)
Explanation:
Possible Pairs : (9,10)(4,6)
sum = (19)(10) maximum pair
sum = 19 (6,10)(4,9)
sum = (16)(15)
maximum pair sum = 16 (4,10)(6,9)
sum = (14)(17)
maximum pair sum = 14
Thus partition (4,10)(6,9) has the minimum of the maximum pair sum of all possible partitions.

Input : arr[] = {10, 7, 2, 6}
Output : (2,10)(6,7)

Approach: Use greedy approach to form the pairs that will result in the minimum of maximum pair sum of all possible partitions. Following steps will help in solving this problem:

Sort the array.
Form N pairs using first and last element, second and second last and so on.
Print the N pairs formed.

Below is the implementation of the above approach:

// Java program to divide the array
// into N pairs such that it has minimum of
// maximum pair sum of possible partitions

import java.io.*;
import java.util.*;
import java.lang.*;

public class Cpp {

      // Function to divide the array into N pairs
      // such that it has minimum of maximum pair sum possible
      static void divideArray(int[] arr, int len) 
      {
             // sort the array
             Arrays.sort(arr);
            
             for (int i = 0; i < len / 2; i++) {
                  System.out.print("(" + arr[i] + "," + arr[len-1-i] + ")");
             }
      }

      //  Driver code
      public static void main(String args[]) 
      {
             int[] arr = {6, 9, 4, 10};

             // length of the array
             int len = arr.length;

             divideArray(arr, len);
      }
}

Output:

(4,10)(6,9)

Time complexity: O(nlogn), due to sorting.

Please write comments if you find anything incorrect. A gentle request to share this topic on your social media profile.