Particiones mínimas de tamaño máximo 2 y suma limitada por valor dado

Dada una array arr[] de números positivos, encuentre el número mínimo de conjuntos en la array que satisfagan la siguiente propiedad, 
1. Un conjunto puede contener un máximo de dos elementos. Los dos elementos no necesitan ser contiguos. 
2. La suma de los elementos del conjunto debe ser menor o igual que la Clave dada. Se puede suponer que la clave dada es mayor o igual que el elemento de array más grande.
Ejemplos:

Input: arr[] = [10, 20, 12], key = 25
Output: 2
We break into two parts {10, 12} and {2}

Input : arr[] = [3, 5, 3, 4], key=5
Output : 4
Explanation: 4 sets (3), (5), (3), (4)

La idea es ordenar primero la array y luego seguir el enfoque de dos punteros. Comenzamos dos punteros desde dos esquinas de la array ordenada. Si su suma es menor o igual a la clave dada, entonces hacemos un conjunto de ellos, de lo contrario, consideramos el último elemento solo.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to count minimum number of partitions
// of size 2 and sum smaller than or equal to given
// key.
#include <algorithm>
#include <iostream>
using namespace std;
 
int minimumSets(int arr[], int n, int key)
{
    int i, j;
 
    // sort the array
    sort(arr, arr + n);
 
    // if sum of ith smaller and jth larger element is
    // less than key, then pack both numbers in a set
    // otherwise pack the jth larger number
    // alone in the set
    for (i = 0, j = n - 1; i <= j; ++i)
        if (arr[i] + arr[j] <= key)
            j--;
 
    // After ending of loop i will contain minimum
    // number of sets
    return i;
}
 
int main()
{
    int arr[] = { 3, 5, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 5;
    cout << minimumSets(arr, n, key);
    return 0;
}

// Java program to count minimum number of partitions
// of size 2 and sum smaller than or equal to given
// key.
 
import java.util.Arrays;
class GFG {
 
 
static int minimumSets(int arr[], int n, int key)
{
    int i, j;
 
    // sort the array
    Arrays.sort(arr);
 
    // if sum of ith smaller and jth larger element is
    // less than key, then pack both numbers in a set
    // otherwise pack the jth larger number
    // alone in the set
    for (i = 0, j = n - 1; i <= j; ++i)
        if (arr[i] + arr[j] <= key)
            j--;
 
    // After ending of loop i will contain minimum
    // number of sets
    return i;
}
 
 
 
    public static void main (String[] args) {
    int []arr = { 3, 5, 3, 4 };
    int n =arr.length;
    int key = 5;
    System.out.println( minimumSets(arr, n, key));
    }
}
// This code is contributed by chandan_jnu.

# Python 3 program to count minimum number
# of partitions of size 2 and sum smaller
# than or equal to given key.
 
def minimumSets(arr, n, key):
     
    # sort the array
    arr.sort(reverse = False)
 
    # if sum of ith smaller and jth larger
    # element is less than key, then pack
    # both numbers in a set otherwise pack
    # the jth larger number alone in the set
    j = n - 1
    for i in range(0, j + 1, 1):
        if (arr[i] + arr[j] <= key):
            j -= 1
 
    # After ending of loop i will
    # contain minimum number of sets
    return i + 1
 
# Driver Code
if __name__ == '__main__':
    arr = [3, 5, 3, 4]
    n = len(arr)
    key = 5
    print(minimumSets(arr, n, key))
 
# This code is contributed by
# Shashank_Sharma

// C# program to count minimum
// number of partitions of size
// 2 and sum smaller than or
// equal to given key.
using System;
class GFG
{
 
static int minimumSets(int []arr,
                       int n, int key)
{
    int i, j;
 
    // sort the array
    Array.Sort(arr);
 
    // if sum of ith smaller and
    // jth larger element is less
    // than key, then pack both
    // numbers in a set otherwise
    // pack the jth larger number
    // alone in the set
    for (i = 0, j = n - 1; i <= j; ++i)
        if (arr[i] + arr[j] <= key)
            j--;
 
    // After ending of loop i
    // will contain minimum
    // number of sets
    return i;
}
 
// Driver Code
public static void Main ()
{
    int []arr = { 3, 5, 3, 4 };
    int n =arr.Length;
    int key = 5;
    Console.WriteLine(minimumSets(arr, n, key));
}
}
 
// This code is contributed
// by chandan_jnu.

<?php
// PHP program to count minimum
// number of partitions of size
// 2 and sum smaller than or
// equal to given key.
function minimumSets($arr, $n, $key)
{
    $i; $j;
 
    // sort the array
    sort($arr);
 
    // if sum of ith smaller and
    // jth larger element is less
    // than key, then pack both
    // numbers in a set otherwise
    // pack the jth larger number
    // alone in the set
    for ($i = 0, $j = $n - 1; $i <= $j; ++$i)
        if ($arr[$i] + $arr[$j] <= $key)
            $j--;
        return $i;
}
 
// Driver Code
$arr = array( 3, 5, 3, 4 );
$n = count($arr);
$key = 5;
echo minimumSets($arr, $n, $key);
 
// This code is contributed
// by chandan_jnu   
?>

<script>
 
 
// Javascript program to count minimum number of partitions
// of size 2 and sum smaller than or equal to given
// key.
 
function minimumSets(arr, n, key)
{
    var i, j;
 
    // sort the array
    arr.sort((a,b)=> a-b)
 
    // if sum of ith smaller and jth larger element is
    // less than key, then pack both numbers in a set
    // otherwise pack the jth larger number
    // alone in the set
    for (i = 0, j = n - 1; i <= j; ++i)
        if (arr[i] + arr[j] <= key)
            j--;
 
    // After ending of loop i will contain minimum
    // number of sets
    return i;
}
 
var arr = [3, 5, 3, 4];
var n = arr.length;
var key = 5;
document.write( minimumSets(arr, n, key));
 
</script>

4

Complejidad temporal: O(nlogn)
 Espacio auxiliar: O(1)