The i-th person has weight people[i], and each boat can carry a maximum weight of limit.
Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most limit.
Return the minimum number of boats to carry every given person.  (It is guaranteed each person can be carried by a boat.)
 

Example 1:
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)


Example 2:
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)


Example 3:
Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)
Note:

1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Sorting

Amortized analysis

Greedy algorithms

Starter code: class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        

Solutions:
class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		lo = 0
		hi = len(people) - 1
		count = 0
		while lo <= hi:
			count += 1
			if people[lo] + people[hi] <= limit:
				lo += 1
			hi -= 1
		return count


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		boats = 0
		l = 0
		r = len(people) - 1
		while r > l:
			boats += 1
			if people[l] + people[r] <= limit:
				l += 1
				r = r - 1
			else:
				r = r - 1
		if r == l:
			boats += 1
		return boats


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people = sorted(people, reverse=True)
		i = 0
		j = len(people) - 1
		n = 0
		while True:
			if i >= j:
				break
			n += 1
			w1 = people[i]
			i += 1
			rem = limit - w1
			if rem >= people[j]:
				j -= 1
		if i == j:
			n += 1
		return n


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		p1 = 0
		p2 = len(people) - 1
		boat = 0
		while p1 <= p2:
			boat += 1
			if people[p1] + people[p2] <= limit:
				p1 += 1
			p2 -= 1
		return boat


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		i = 0
		j = len(people) - 1
		count = 0
		while i < j:
			if people[i] + people[j] <= limit:
				count += 1
				i += 1
				j -= 1
			else:
				count += 1
				j -= 1
		if i == j:
			count += 1
		return count


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		new = sorted(people)
		(i, j) = (0, len(people) - 1)
		res = 0
		while i <= j:
			if new[j] + new[i] <= limit:
				i += 1
			j -= 1
			res += 1
		return res


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		(l, r) = (0, len(people) - 1)
		res = 0
		while l <= r:
			while l <= r and people[l] + people[r] > limit:
				res += 1
				r -= 1
			if l <= r:
				res += 1
				l += 1
				r -= 1
		return res


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		length = len(people)
		people.sort()
		left = 0
		right = length - 1
		boat_num = 0
		while left <= right:
			if people[left] + people[right] <= limit:
				left += 1
				right -= 1
			else:
				right -= 1
			boat_num += 1
		return boat_num


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		if not people:
			return 0
		people = sorted(people)
		left = 0
		right = len(people) - 1
		board_cnt = 0
		while left <= right:
			if left == right:
				board_cnt += 1
				break
			if people[left] + people[right] <= limit:
				left += 1
				right -= 1
				board_cnt += 1
			else:
				right -= 1
				board_cnt += 1
		return board_cnt


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		(left, right) = (0, len(people) - 1)
		boats = 0
		while left <= right:
			if left == right:
				boats += 1
				break
			if people[left] + people[right] <= limit:
				boats += 1
				left += 1
				right -= 1
			else:
				right -= 1
				boats += 1
		return boats


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		start = 0
		end = len(people) - 1
		ans = 0
		while start <= end:
			ans += 1
			if people[start] + people[end] <= limit:
				start += 1
			end -= 1
		return ans


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort(reverse=True)
		(l, r) = (0, len(people) - 1)
		while l <= r:
			if people[l] + people[r] <= limit:
				r -= 1
			l += 1
		return l


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people = sorted(people)
		count = 0
		left = 0
		right = len(people) - 1
		while left <= right:
			cur = people[left] + people[right]
			if cur <= limit:
				left += 1
				right -= 1
			elif cur > limit:
				right -= 1
			count += 1
		return count


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		boats = 0
		people = sorted(people)
		print(people)
		(i, j) = (0, len(people) - 1)
		while i <= j:
			if people[i] + people[j] > limit:
				j -= 1
			else:
				i += 1
				j -= 1
			boats += 1
		return boats


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		s = []
		c = 0
		people.sort(reverse=True)
		for i in range(len(people)):
			if s and people[i] < s[-1]:
				s[-1] = s[-1] - people[i]
				s.pop()
			elif s and people[i] == s[-1]:
				s.pop()
			elif s and people[i] > s[-1]:
				s.append(limit - people[i])
				c += 1
			elif people[i] == limit:
				c += 1
			else:
				c += 1
				s.append(limit - people[i])
		return c


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		less_than_half = dict()
		more_than_half = dict()
		half = 0
		total_boats = 0
		for person in people:
			diff = limit - person
			if diff == 0:
				total_boats += 1
				continue
			if person < limit / 2:
				if diff in more_than_half:
					total_boats += 1
					if more_than_half[diff] == 1:
						del more_than_half[diff]
					else:
						more_than_half[diff] -= 1
				elif person in less_than_half:
					less_than_half[person] += 1
				else:
					less_than_half[person] = 1
			elif person > limit / 2:
				if diff in less_than_half:
					total_boats += 1
					if less_than_half[diff] == 1:
						del less_than_half[diff]
					else:
						less_than_half[diff] -= 1
				elif person in more_than_half:
					more_than_half[person] += 1
				else:
					more_than_half[person] = 1
			elif half == 1:
				total_boats += 1
				half = 0
			else:
				half = 1
		less_keys = sorted(less_than_half.keys())
		more_keys = sorted(list(more_than_half.keys()), reverse=True)
		while len(less_keys) and len(more_keys):
			if less_keys[0] + more_keys[0] <= limit:
				if less_than_half[less_keys[0]] < more_than_half[more_keys[0]]:
					total_boats += less_than_half[less_keys[0]]
					more_than_half[more_keys[0]] -= less_than_half[less_keys[0]]
					less_keys.pop(0)
				elif less_than_half[less_keys[0]] > more_than_half[more_keys[0]]:
					total_boats += more_than_half[more_keys[0]]
					less_than_half[less_keys[0]] -= more_than_half[more_keys[0]]
					more_keys.pop(0)
				else:
					total_boats += less_than_half[less_keys[0]]
					less_keys.pop(0)
					more_keys.pop(0)
			else:
				total_boats += more_than_half[more_keys[0]]
				more_keys.pop(0)
		less_total = 0
		for k in less_keys:
			less_total += less_than_half[k]
		more_total = 0
		for k in more_keys:
			more_total += more_than_half[k]
		total_boats += (less_total + half + 1) // 2 + more_total
		return total_boats


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort(reverse=True)
		first_index = 0
		second_index = len(people) - 1
		ans = 0
		while first_index <= second_index:
			if people[first_index] + people[second_index] <= limit:
				second_index -= 1
			first_index += 1
			ans += 1
		return ans


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people = sorted(people)
		i = 0
		j = len(people) - 1
		total = 0
		while i <= j:
			if i == j:
				total += 1
				i += 1
				j -= 1
			elif people[i] + people[j] <= limit:
				i += 1
				j -= 1
				total += 1
			else:
				j -= 1
				total += 1
		return total


class Solution:

	def numRescueBoats(self, people: List[int], cap: int) -> int:
		people.sort()
		N = len(people)
		(i, j) = (0, N - 1)
		ans = 0
		k = cap
		s = 2
		while i <= j:
			while s and j >= 0:
				if k - people[j] < 0:
					break
				k -= people[j]
				j -= 1
				s -= 1
			while s and i < N:
				if k - people[i] < 0:
					break
				k -= people[i]
				i += 1
				s -= 1
			k = cap
			s = 2
			ans += 1
		return ans


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		sorted_people = list(sorted(people, reverse=True))
		i = 0
		j = len(people) - 1
		while i <= j:
			if sorted_people[i] + sorted_people[j] <= limit:
				j -= 1
			i += 1
		return i


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		count = len(people)
		end = len(people) - 1
		begin = 0
		res = 0
		while count > 0:
			if people[end] + people[begin] <= limit:
				res += 1
				count -= 2
				end -= 1
				begin += 1
			else:
				res += 1
				count -= 1
				end -= 1
		return res


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		groups = self.group_people_by_weight(people, limit)
		return self.count_num_boats(groups, limit)

	def group_people_by_weight(self, people, limit):
		groups = [0] * (limit + 1)
		for person_weight in people:
			groups[person_weight] += 1
		return groups

	def count_num_boats(self, groups, limit):
		num_boats = 0
		start = 0
		end = len(groups) - 1
		while start <= end:
			while start <= end and groups[start] <= 0:
				start += 1
			while start <= end and groups[end] <= 0:
				end -= 1
			if start > end:
				break
			if start + end <= limit:
				groups[start] -= 1
			groups[end] -= 1
			num_boats += 1
		return num_boats


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		low = 0
		up = len(people) - 1
		boats = 0
		while low <= up:
			if up - 1 >= low and people[up] + people[up - 1] <= limit:
				up -= 2
				boats += 1
			elif up != low and people[up] + people[low] <= limit:
				up -= 1
				low += 1
				boats += 1
			else:
				up -= 1
				boats += 1
		return boats


from collections import deque

class Solution:

	def numRescueBoats(self, people, limit):
		n = len(people)
		weights = deque(sorted(people))
		boat = 0
		while n > 1:
			if weights[0] + weights[-1] <= limit:
				weights.popleft()
				weights.pop()
				n -= 2
			else:
				weights.pop()
				n -= 1
			boat += 1
		if n == 1:
			boat += 1
		return boat


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		l = 0
		h = len(people) - 1
		remain_capacity = limit
		if len(people) == 0:
			return 0
		boat = 1
		ppl_in_boat = 2
		while l <= h:
			if people[h] <= remain_capacity and ppl_in_boat != 0:
				remain_capacity -= people[h]
				ppl_in_boat -= 1
				h = h - 1
			elif remain_capacity >= people[l] and ppl_in_boat != 0:
				remain_capacity -= people[l]
				ppl_in_boat -= 1
				l = l + 1
			else:
				boat += 1
				remain_capacity = limit
				ppl_in_boat = 2
		return boat


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		n = len(people)
		people.sort()
		print(people)
		i = 0
		j = n - 1
		re = []
		c = 0
		tmp = []
		while i <= j:
			if people[i] + people[j] > limit:
				c += 1
				tmp.append(people[j])
				re.append(tmp)
				tmp = []
				j = j - 1
			else:
				tmp.append(people[i])
				tmp.append(people[j])
				re.append(tmp)
				tmp = []
				i = i + 1
				j = j - 1
		print(re)
		return len(re)


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		if people[0] >= limit:
			return 0
		res = [0]
		(i, j) = (0, len(people) - 1)
		num_people = 0
		while i <= j:
			if res[-1] + people[j] <= limit and num_people < 2:
				res[-1] += people[j]
				j -= 1
				num_people += 1
			elif res[-1] + people[i] <= limit and num_people < 2:
				res[-1] += people[i]
				i += 1
				num_people += 1
			else:
				res.append(0)
				num_people = 0
		return len(res)


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		num_boats = 0
		last = len(people) - 1
		first = 0
		while first < last:
			if people[first] + people[last] <= limit:
				last -= 1
				first += 1
				num_boats += 1
			else:
				num_boats += 1
				last -= 1
		if first == last:
			num_boats += 1
		return num_boats


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		l = len(people)
		if l <= 1:
			return 1
		people.sort()
		i = 0
		j = l - 1
		c = 0
		while i < j:
			print((i, j, c))
			if people[i] + people[j] <= limit:
				c += 1
				i += 1
				j -= 1
			else:
				j -= 1
				c += 1
		if i == j:
			c += 1
		return c

	def sortPeople(self, arr):
		l = len(arr)
		if l <= 1:
			return arr
		pivot = arr[l - 1]
		larr = []
		rarr = []
		for i in range(l - 1):
			if arr[i] >= pivot:
				rarr.append(arr[i])
			else:
				larr.append(arr[i])
		return self.sortPeople(larr) + [pivot] + self.sortPeople(rarr)


class Solution(object):

	def numRescueBoats(self, people, limit):
		people.sort()
		(i, j) = (0, len(people) - 1)
		ans = 0
		while i <= j:
			ans += 1
			if people[i] + people[j] <= limit:
				i += 1
			j -= 1
		return ans


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		if len(people) == 0 or len(people) == 1:
			return len(people)
		else:
			lptr = 0
			rptr = len(people) - 1
			count = 0
			while lptr <= rptr:
				if people[lptr] + people[rptr] <= limit:
					count += 1
					lptr += 1
					rptr -= 1
				else:
					rptr -= 1
					count += 1
			return count


from collections import deque

class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people = deque(sorted(people))
		count = 0
		while len(people) > 1:
			lightest = people.popleft()
			heaviest = people.pop()
			if lightest + heaviest <= limit:
				count += 1
				continue
			else:
				if lightest < limit:
					people.appendleft(lightest)
				else:
					count += 1
				count += 1
		return count + len(people)


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort(reverse=True)
		res = 0
		i = 0
		j = len(people) - 1
		while i <= j:
			if people[i] + people[j] <= limit:
				j -= 1
			i += 1
		return i


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		lo = 0
		count = 0
		for hi in range(len(people))[::-1]:
			if lo < hi and people[lo] + people[hi] <= limit:
				lo += 1
			if lo == hi:
				return len(people) - hi


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		n = len(people)
		i = 0
		j = n - 1
		boats = 0
		while i <= j:
			if people[i] + people[j] <= limit:
				i += 1
			j -= 1
			boats += 1
		return boats


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people = sorted(people)
		count = 0
		(i, j) = (0, len(people) - 1)
		while 0 <= i < j < len(people):
			while 0 <= i < j < len(people) and people[i] + people[j] > limit:
				j -= 1
				count += 1
			i += 1
			j -= 1
			count += 1
		if i == j:
			count += 1
		return count


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		minBoats = 0
		people.sort()
		left = 0
		right = len(people) - 1
		while left <= right:
			if people[left] + people[right] <= limit:
				left += 1
			minBoats += 1
			right -= 1
		return minBoats


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		ret = 0
		people.sort(reverse=True)
		start = len(people) - 1
		for i in range(len(people)):
			if start >= i:
				ret += 1
			temp_lim = limit - people[i]
			for j in range(start, i, -1):
				if people[j] <= temp_lim:
					start = j - 1
					break
				elif people[j] > temp_lim:
					start = j
					break
			print(temp_lim)
		return ret


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		print(people)
		boats = 0
		left_index = 0
		right_index = len(people) - 1
		while left_index <= right_index:
			if people[left_index] + people[right_index] <= limit:
				left_index += 1
			boats += 1
			right_index -= 1
		return boats


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people = sorted(people)
		left = 0
		right = len(people) - 1
		counter = 0
		while left < right:
			total = people[left] + people[right]
			counter += 1
			right -= 1
			if total <= limit:
				left += 1
		if left == right:
			counter += 1
		return counter


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		total = 0
		people.sort()
		print(people)
		i = 0
		j = len(people) - 1
		while i <= j:
			print(j)
			if people[i] + people[j] > limit or i == j:
				j -= 1
				total += 1
			else:
				i += 1
				j -= 1
				total += 1
		return total


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		bucket = [0] * (limit + 1)
		for i in people:
			bucket[i] += 1
		start = 0
		end = len(bucket) - 1
		count = 0
		while start <= end:
			while start <= end and bucket[start] <= 0:
				start += 1
			while start <= end and bucket[end] <= 0:
				end -= 1
			if bucket[start] <= 0 and bucket[end] <= 0:
				break
			count += 1
			if start + end <= limit:
				bucket[start] -= 1
			bucket[end] -= 1
		return count


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		if people == None or len(people) == 0:
			return 0
		people.sort()
		start = 0
		end = len(people) - 1
		counter = 0
		while start <= end:
			if people[start] + people[end] <= limit:
				start += 1
				end -= 1
			else:
				end -= 1
			counter += 1
		return counter


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		q = collections.deque(sorted(people))
		ans = 0
		while len(q) > 1:
			(i, x) = (q.pop(), q[0])
			if i + x <= limit:
				q.popleft()
			ans += 1
		return ans + (1 if q else 0)


import heapq

class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		(i, j) = (0, len(people) - 1)
		ans = 0
		while i <= j:
			ans += 1
			if people[i] + people[j] <= limit:
				i += 1
			j -= 1
		return ans


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		p1 = 0
		p2 = len(people) - 1
		count = 1
		cur = 0
		curNum = 0
		while p1 <= p2:
			if people[p2] <= limit - cur and curNum < 2:
				cur = cur + people[p2]
				curNum += 1
				p2 -= 1
				continue
			if people[p1] <= limit - cur and curNum < 2:
				cur = cur + people[p1]
				curNum += 1
				p1 += 1
				continue
			count += 1
			cur = 0
			curNum = 0
		return count


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people = sorted(people, reverse=True)
		boats = 0
		left = 0
		right = len(people) - 1
		while left <= right:
			if people[left] + people[right] <= limit:
				right -= 1
			left += 1
			boats += 1
		return boats


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		if not people or limit == 0:
			return 0
		ans = 0
		people.sort()
		(left, right) = (0, len(people) - 1)
		while left <= right:
			if people[left] + people[right] <= limit:
				left += 1
				right -= 1
			else:
				right -= 1
			ans += 1
		return ans


from collections import Counter

class Solution:

	def numRescueBoats(self, people, limit):
		people.sort(reverse=True)
		boats = 0
		r = len(people) - 1
		l = 0
		while l <= r:
			boats += 1
			if people[l] + people[r] <= limit:
				r -= 1
			l += 1
		return boats


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		heap = []
		people.sort()
		heap.append((people[len(people) - 1], 1))
		i = len(people) - 2
		while i >= 0:
			ele = people[i]
			if limit >= ele + heap[0][0] and heap[0][1] < 2:
				minimum = heapq.heappop(heap)
				heapq.heappush(heap, (float('inf'), 2))
			else:
				heapq.heappush(heap, (ele, 1))
			i -= 1
		print(heap)
		return len(heap)


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people = sorted(people)
		l = 0
		r = len(people) - 1
		ret = 0
		while l < r:
			if people[r] >= limit:
				ret += 1
				r -= 1
			elif people[r] + people[l] > limit:
				ret += 1
				r -= 1
			else:
				ret += 1
				l += 1
				r -= 1
		if l == r:
			ret += 1
		return ret


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort()
		N = len(people)
		num_boats = 0
		if len(people) == 1:
			return 1
		less_than_half = [p for p in people if p <= limit / 2]
		more_than_half = [p for p in people if p > limit / 2]
		while len(more_than_half) > 0 and len(less_than_half) > 0:
			if more_than_half[-1] + less_than_half[0] > limit:
				more_than_half.pop(-1)
				num_boats += 1
				continue
			else:
				more_than_half.pop(-1)
				less_than_half.pop(0)
				num_boats += 1
				continue
		num_boats += len(more_than_half)
		num_boats += int(len(less_than_half) / 2 + 0.5)
		return num_boats


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		sortedPeople = sorted(people)
		i = 0
		j = len(sortedPeople) - 1
		count = 0
		while i <= j:
			if i == j:
				count += 1
				i += 1
				j -= 1
				continue
			if sortedPeople[i] + sortedPeople[j] <= limit:
				count += 1
				i += 1
				j -= 1
			else:
				count += 1
				j -= 1
		return count


class Solution:

	def numRescueBoats(self, people, limit):
		people.sort()
		(i, j) = (0, len(people) - 1)
		ans = 0
		while i <= j:
			ans += 1
			if people[i] + people[j] <= limit:
				i += 1
			j -= 1
		return ans

	def numRescueBoats2(self, people: List[int], limit: int) -> int:
		self.ans = 9999
		visited = [0 for _ in range(len(people) + 1)]

		def traverse(ind: int, boatCnt: int, boats):
			if visited[ind]:
				return
			if ind == len(people):
				if boatCnt + 1 < self.ans:
					print(boats)
					self.ans = boatCnt + 1
			else:
				visited[ind] = 1
				for i in range(ind + 1, len(people) + 1):
					b = boats[:]
					if boatCnt >= len(b):
						b.append([])
					if sum(b[boatCnt]) + people[ind] > limit:
						boatCnt += 1
						if boatCnt >= len(b):
							b.append([])
					b[boatCnt].append(people[ind])
					traverse(ind + 1, boatCnt, b)
				visited[ind] = 0
		traverse(0, 0, [])
		return self.ans


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		people.sort(reverse=True)
		boats = people[:(1 + len(people)) // 2]
		onboard = [1] * len(boats)
		i = 0
		j = len(boats)
		k = len(people) - 1
		while j <= k:
			if i == len(boats):
				boats.append(people[j])
				j += 1
				if j > k:
					break
			target = limit - boats[i]
			if people[k] > target:
				i += 1
				if i == len(boats):
					boats.append(people[j])
					j += 1
			else:
				boats[i] += people[k]
				k -= 1
				i += 1
		return len(boats)


class Solution:

	def numRescueBoats(self, people: List[int], limit: int) -> int:
		left = 0
		right = len(people) - 1
		boat = 0
		people.sort()
		while left <= right:
			if left == right:
				boat += 1
				break
			elif people[left] + people[right] <= limit:
				left += 1
			right -= 1
			boat += 1
		return boat