Algorytm wyznaczający zbiory

Mógłby ktoś poradzić, jak powinien działać algorytm podany w tym zadaniu? Wiem tylko, że na początku trzeba posortować dane najoptymalniejszą metodą, ale nie wiem co zrobić później :/

Treść zadania:
Na wejściu danych jest n (1≤n≤100) różnych liczb N+ z przedziału [1,k] (1≤k≤150). Zaimplementuj algorytm(o możliwie najniższym koszcie czasowym), który wykorzystując zadane liczby, generuje zbiory 2-elementowe {x,y} spełniające własność x+y<=k. Każdą liczbę należy użyć dokładnie jeden raz. W przypadku, gdy dla zadanejwartości x nie można już znaleźć takiej liczby y, by spełniona była powyższą własność, należy utworzyć zbiór 1-elementowy {x}. Zadanie polega na znalezieniu możliwie najmniejszej ilości tego typu zbiorów.

Z góry dzięki za pomoc ;)

Optymalny = najlepszy. Nie ma czegoś takiego jak "najoptymalniejszy". Albo coś jest optymalne albo nie jest i tyle.
Jeśli chodzi o zadanie to leciałbym od największych liczb, tzn dla największej liczby X wziąłbym największego możliwego Y żeby nierówność była spełniona.
Najprościej będzie zrobić z tego zrównoważone drzewo binarne O(nlogn) a następnie lecieć po kolei po węzłach od największego klucza i szukać dla niego największego Y żeby nierówność była spełniona. Tzn dla danego X szukamy w drzewie Y=k-X. Nawet jeśli klucza w drzewie nie ma to dostaniemy najbliższy mniejszy klucz i jego bierzemy jako Y i usuwamy oba z drzewa. Daje nam to O(nlogn) na szukanie Y. Wszystko co zostanie w drzewie po przeiterowaniu zostaje osobnymi zbiorami.

Możne analogicznie posortować dane (O(nlogn)) a następnie dla każdego X szukać tak samo Y=k-X ale za pomocą szukania binarnego i znów wybierać klucz mniejszy lub równy szukanemu Y. Tak samo da nam to O(nlogn) bo n razy szukamy binarnie (O(logn)).

Można to zrobić szybciej.
Na początku sortujemy przez zliczanie, co daje czas O(n) (O(n + k), ale tutaj n i k są podobne). Gdy posortujemy, to idziemy sobie dwoma wskaźnikami - jednym od końca w lewo, a drugim od początku. Gdy znajdziemy sumę spełniającą tą nierówność, to oba wskaźniki "podchodzą" do siebie, jeżeli jednak jest za duża, to tym wskaźnikiem, który szedł od prawej strony idziemy o jeden w lewo, itd. Łącznie złożoność O(n), ewentualnie jeżeli zastosujesz algorytm sortowania w czasie O(n log n), to wtedy przez nie jest zdominowana złożoność, chociaż jak widać i tutaj jeżeli k by było duże, to się nie opłaca przez zliczanie. Generalnie dane są bardzo małe jak na takie zadanie i w żaden sposób nie sprawdzą złożoności, nawet O(n^3) by przeszedł.