All problems

Boats to Save People

Medium · two pointers

A rescue crew has to carry a group of people across a flooded road. The list people holds each person's weight, listed from lightest to heaviest (equal weights may repeat).

Every boat carries at most two people, and the combined weight in a boat must not be more than limit. Each person weighs at most limit, so anyone can always travel alone.

Return the smallest number of boats that carries everyone.

Examples

Example 1

Input: people = [2, 3, 4, 5], limit = 7

Output: 2

Put 2 with 5 (7) in one boat and 3 with 4 (7) in the other.

Example 2

Input: people = [3, 5, 5, 6], limit = 8

Output: 3

Only 3 and 5 fit together (8). One boat takes 3 and a 5, one takes the other 5, and one takes 6.

Example 3

Input: people = [9], limit = 9

Output: 1

A single person fits in a single boat.

Constraints