Minimum Number of Boats

You get an array weights. Each number is the weight of one student. You also get two limits, maxWeight and maxDiff.

All the students must cross a river by boat. There are as many boats as needed. Return the smallest number of boats that takes everyone across.

A boat carries one student or two. Two students can share a boat only if their weights add up to at most maxWeight. Their weights must also differ by at most maxDiff.

Example 1:

Input: weights = [3, 5, 4, 6], maxWeight = 9, maxDiff = 1
Output: 3
Explanation: One way is (3, 4), (5) and (6).
5 and 6 can't share a boat.
Together they weigh 11, more than 9.

Example 2:

Input: weights = [2, 9, 1, 8], maxWeight = 10, maxDiff = 3
Output: 3
Explanation: The boats are (1, 2), (8) and (9).
(1, 9) and (2, 8) are light enough.
But their weights differ by more than 3.

Example 3:

Input: weights = [12, 5, 4], maxWeight = 10, maxDiff = 2
Output: 2
Explanation: 4 and 5 share a boat.
The student who weighs 12 rides alone.

Constraints:

• 1 to 30,000 students.
• Each weight is from 0 to 100,000,000.
• maxWeight is from 1 to 100,000.
• maxDiff is from 1 to 10,000.
• A student may weigh more than maxWeight. That student rides alone.