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

Difficulty: interview

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:
            # TODO - Check for [5,5,5,5,5] with limit of 5
            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:
        people.sort()
        i=0
        j=len(people)-1
        count=0
        while(i<=j):
            count+=1
            if(people[i]+people[j]<=limit):
                i+=1
            j-=1
        return count


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:
            #key
            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()
        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:
        if len(people) <= 1:
            return 0
        people.sort()
        boats = 0
        l = 0
        r = len(people) - 1
        while l <= r:
            if l == r:
                return boats + 1
            if people[l] + people[r] <= limit:
                boats += 1
                l += 1
                r -= 1
            else:
                boats += 1
                r -= 1
        return boats


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

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


class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        # start at ends and move inward
        
        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:
        j = len(people)-1
        i = 0
        people = sorted(people)
        ### since we could max have two people on a boat so we need to add have two ###pointers
        print(people)
        count = 0
        while(i<=j):
            count = count+1
            if people[j] + people[i]<=limit:
                i = i + 1
                j = j - 1
            else:
                j = j - 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
                else:
                    if 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
                else:
                    if person in more_than_half:
                        more_than_half[person] += 1
                    else:
                        more_than_half[person] = 1
            else:
                if 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]
        
        # we can pair up each of the less than half weights
        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
            else:
                if people[i] + people[j] <= limit:
                    i += 1
                    j -= 1
                    total += 1
                else:
                    j -= 1
                    total += 1
        return total
        # print(people)
        # while i < len(people):
        #     print(i,people)
        #     if i < len(people) - 1 and people[i] + people[i+1] <= limit:
        #         print(\"two peeps\")
        #         i += 2
        #     else:
        #         print(\"one peep\")
        #         i += 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:
            # prioritize heavier one
            while s and j >= 0:
                if k - people[j] < 0:
                    break
                k -= people[j]
                j -= 1
                s -= 1
            # check if we can fit any remainig lighter people
            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:
        num_boats = 0
        counts = [0] * (limit + 1)
        for person_weight in people:
            counts[person_weight] += 1
        
        start = 0
        end = len(counts) - 1
        while start <= end:
            while start <= end and counts[start] <= 0:
                start += 1
            while start <= end and counts[end] <= 0:
                end -= 1
            if start > end:
                break
            if start + end <= limit:
                counts[start] -= 1
            counts[end] -= 1
            num_boats += 1
        return num_boats

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        print(people)
        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
                added = True
            else:
                up -= 1
                boats += 1
                
        return boats


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()
        i,j=0,len(people)-1
        answer=0
        while i<j:
            if people[i]+people[j]<=limit:
                i+=1
                j-=1
            else:
                j-=1
            if i==j:
                answer+=1
            answer+=1
        return answer
                


class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        i = 0
        j = 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()
        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:
        people.sort()
        
        left=0
        right=len(people)-1
        boats = 0
    
        while left<=right:
            if left==right:
                boats+=1
                break
            if people[left] + people[right] <= limit:
                left+=1
            #     right-=1
            #     boats+=1
            # else:
            #     right-=1
            #     boats+=1
            right-=1
            boats+=1
        
        return boats
                


class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        l = len(people)
        if (l <= 1):
            return(1)
#        people = self.sortPeople(people)
        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):
   #     print(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])
       # print(larr + [pivot] + rarr)
        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()
        l = 0
        r = len(people)-1
        res = 0
        while l <=r:
            if people[l]+people[r] <= limit:
                res+=1
                l+=1
                r-=1
            else:
                res+=1
                r-=1
        return res

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


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 
            '''
        people.sort()        
        left = 0
        right = len(people) - 1
        
        counter = 0
        while left <= right:
            if people[left] + people[right] <= limit:
                left += 1
                right -= 1
                counter += 1
            else: # people[left] + people[right] > limit:
                right -= 1
                counter += 1
            return counter'''


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()
        
        l, r = 0, len(people)-1
        res = 0
        
        while l <= r:
            res += 1
            if people[l] + people[r] <= limit:
                l += 1
            r -= 1
        return res
        


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


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:
        
        '''
        time complexity :
            because of sorting O(Nlog(N))
            the second loop is smaller so we ignore it
        
        space complexity:
            because of sorting
            O(N)
        '''
        people.sort()
        left = 0
        right = len(people)-1
        boat_number = 0

        while left <= right:
            if left == right:
                boat_number += 1
                break
            if people[left] + people[right] <= limit:
                left += 1
                right -= 1
                boat_number+=1
            else:
                right -= 1
                boat_number +=1

        return boat_number

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, hi = 0, len(people) -1
        boats = 0
        
        while lo <= hi:
            cap = limit
            cap -= people[hi] # always take the higher one first
            hi -= 1
            
            if people[lo] <= cap: # if you can take a lower one to pair with higher, then include it
                lo += 1
                
            boats += 1 # increment boat by 1, whether you can only take hi or lo + hi
            
        return boats
        
        


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 = sorted(people)
        i = 0
        j = len(people)-1
        res = 0
        while i<=j:
            res+=1
            if people[i]+people[j]<=limit:
                i+=1
            j-=1
        return res

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

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
            # else:
            #     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()
        i, j = 0, len(people)-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.sort()
        i=0
        j=len(people)-1
        m=0
        while(i<=j):
            if people[i]+people[j]<=limit:
                i+=1
                j-=1
            else:
                j=j-1
            m+=1    
        return m        

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 i < j and people[i] + people[j] <= limit:
                i += 1
                j -= 1
            else:
                j -= 1
            
            boats += 1
            
        return boats

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        # Map: of weight to count O(n)
        # Check limit down
        
        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.sort()
        i=0
        j=len(people)-1
        boats=0
        while(i<=j):
            if people[i]+people[j]<=limit:
                i+=1
                j-=1
            elif people[i]+people[j]>limit:
                j-=1
            boats+=1
        return boats


# 1, 2, 2, 3 limit = 4
# l        r


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 #if len(people)%2 == 0 else 1
        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:
        
        people.sort(reverse=True)
        res = 0
        print(people)
        l, r = 0, len(people)-1
        
        while(l<=r):
            
            print((l, r))
            remain = limit-people[l]
            res += 1
            l += 1
            if remain - people[r] >= 0:
                remain -= people[r]
                r -= 1
                    
                    
        print(res)
        
        return res





class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        
#         start=0
#         end=len(people)-1
#         count=0
#         #people=sorted(people)
#         while start<=end:
#             if people[start]+people[end]<=limit:
#                 start+=1
            
#             end-=1
#          count+=1
        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:
        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()
        left, right = 0, len(people) - 1
        count = 0
        while left <= right:
            if people[left] + people[right] <= limit:
                left += 1
                right -= 1
                count += 1
            else:
                right -= 1
                count += 1
        return count

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        i, j = 0, len(people) -1

        count = 0

        while i <= j:
            if i == j:
                count += 1
                break
            if people[i] + people[j] <= limit:
                i+=1
                j-=1
            else:
                j-=1
            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:
                minBoats += 1
                left += 1
                right -= 1
            elif people[left] + people[right] > limit:
                minBoats += 1
                right -= 1
                
        return minBoats

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


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 = count + 1
                j = j - 1
            else:
                count = count + 1
                i = i + 1
                j = j - 1
        return(count)
                


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)
            
        


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

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        total = 0 #if len(people)%2 == 0 else 1
        people.sort()
        i = 0 
        j = len(people) - 1
        while i <= 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:
        people.sort()
        i,j = 0, 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
        return count


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



'''

            
        
        
'''



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:
        # sort 1 - sort in the ascending order of weight
        people.sort()
        boats = 0
        i = 0
        j = len(people) - 1
        while j>=i:
            # check if two people can sit in a boat
            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, 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:
        people = sorted(people)
        i,j = 0, len(people)-1
        c = 0
        while i <= j:
            if people[j] + people[i] <= limit:
                i += 1
            j -= 1
            c += 1
        return c

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
            else:
                right -= 1
                boat += 1
        
        return boat


class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        i=0
        j=len(people)-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:
        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) # sort in descending order
        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


# O(nlogn) time and O(1) space
# Greedy approach: pair the heaviest person with the lightest
# Since there are only 2 people on one boat you don't need to \"optimize\" the space of the boat to carry the third person. Moreover, you can show that if you can pair the heaviest with second heaviest, you can essentially pair any 2 people on the boat (which is the best case scenario).
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        ans = 0
        people.sort()
        l, r = 0, len(people)-1
        while l<= r:
            if people[l] + people[r] <= limit:
                l += 1
            r -= 1
            ans += 1
        
        return ans


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:
                # largest doesn't fit with smallest
                more_than_half.pop(-1)
                num_boats += 1
                continue
                
            else:
                # largest fit with smallest
                more_than_half.pop(-1)
                less_than_half.pop(0)
                num_boats += 1
                continue      
                
        # no more pairings - one of the lists is empty
        num_boats += len(more_than_half)
        num_boats += int(len(less_than_half)/2 +0.5)            
                
        return num_boats

class Solution:
    # Time: O(n*log(n))
    # Time: O(n)
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        i, j = 0, len(people) - 1
        res = 0
        while i <= j:
            res += 1
            if people[i] + people[j] <= limit:
                i += 1
            j -=1
        return res

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        #does sorting help?
        # if we sort, we can use a pointer and continue incrementing until weight is over limit
        
        people.sort()
        boats = 0
        i = 0
        j = len(people) - 1
        
        while i <= j:
            boats += 1
            if people[i] + people[j] <= limit:
                i += 1
                j -= 1
            else:
                j -= 1
            
        return 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, [])
        
        #print(boats)
        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:
    # O(p + plog(p)) = O(p(1 + log(p))) = O(plog(p)) time / O(1) space or memory
    # where 'p' is the number of people
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        
        # 1st step: sort the array of people's weights
        people.sort()
        
        # 2nd step: get the current lightest person, fit on the boat, then try to 
        # put also the lightest person if possible
        # EACH BOAT CARRIES AT MOST 2 PEOPLE
        nb_of_boats = 0
        i, j = 0, len(people) - 1
        
        while i <= j:
            if people[i] + people[j] <= limit:
                i += 1
            j -= 1
            nb_of_boats += 1
        
        return nb_of_boats

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        # sort list
        # set l = 0, r = last
        # see if l+r will fit in boat
        # if too heavy, put r in boat and iterate r     
        
        nboats = 0
        people.sort(reverse=True)
        l = 0
        r = len(people)-1
        while l < r:
            if people[l]+people[r] > limit:
                l += 1
                nboats += 1
                if l == r:
                    nboats += 1
                    break
            else:
                l += 1
                r -= 1
                nboats += 1
                if l == r:
                    nboats += 1
                    break
    
        return nboats

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