Shoes for seahorses

Husk, 15 14 bytes

Γ0(→₀?tI↑<+3)O

Uses the greedy algorithm: sort and pair from the left. Try it online!

Thanks to Leo for saving 1 byte.

Explanation

This is the first Husk answer that uses Γ, the function for pattern matching a list. In this use case, if a is a value and g is a function, then Γag corresponds to the function f defined by the Haskell snippet

f [] = a
f (x:xs) = g x xs

I define the base case as a = 0 and

g x xs = 1 + line0 (if head xs < x+3 then tail xs else xs)

where line0 refers to the entire line. In the Husk code, x and xs are implicit arguments to the lambda function, and line0 is ₀. The list is sorted again in each recursive call, but that doesn't matter in a golf challenge.

Γ0(→₀?tI↑<+3)O
             O  Sort
Γ               and pattern match
 0              giving 0 for an empty list
  (         )   and applying this function to a non-empty list:
          +3     Add 3 to first argument (x),
         <       make a "test function" for being less than that,
        ↑        take values from second argument (xs) while they pass the test.
     ?           If that prefix is nonempty (next value can be paired),
      t          take tail of xs,
       I         otherwise take xs as is.
    ₀            Apply the main function (line0) to this list
   →             and add 1 for the singleton/pair we just processed.

Python 2, 49 bytes

f=lambda a:a>[a.sort()]and-~f(a[[3+a.pop(0)]>a:])

Try it online!

Based on Leaky Nun's recursive solution.

---

Python 2, 59 bytes

p=c=0
for x in sorted(input()):c+=x>p;p=(x>p)*(x+2)
print c

Try it online!

Iterates through the sizes x in sorted order. Remembers the upper threshold p for the current size to the paired with the previous one. If so (x>p), reset the threshold to 0 to make it impossible for the next one to be paired. If not, increment the output count c and set the next threshold p to x+2.

The new threshold p=(x>p)*(x+2) is a bloated expression. I'd like to find a way to shorten it.

05AB1E, 13 bytes

Uses the approach OP described in the comments.

{¥3‹J0¡€gÌ2÷O

Try it online!

Explanation

{¥3‹J0¡€gÌ2÷O   Argument l
{               Sort l
 ¥              Push deltas
  3‹            Map to lower than 3 (1 for true, 0 for false)
    J0¡         Join and split on 0
       €g       Map to length
         Ì      Each + 2
          2÷    Integer division by 2
            O   Sum