python, beginner-friendly, easy understanding 2ptr, sort+greedy✨
Note: the code has an extra list boatlist=[ ] only for the purpose of visualisation for better clarity and understanding.\nboatlist [ ] prints the boats that ca
Note: the code has an extra list boatlist=[ ] only for the purpose of visualisation for better clarity and understanding.\nboatlist [ ] prints the boats that carry people\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSorting helps in applying the two-pointer technique efficiently, allowing us to consider pairs of people whose weights can fit into a boat together. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n two pointers, l and r, initialized to the start and end of the sorted list, respectively. These pointers move towards each other, considering the lightest and heaviest people for each boat.\n\nWhen we pair the lightest and heaviest people, we aim to get as close to the weight limit as possible without exceeding it.\n\n(for more clarity you can try to look at the boatlist in my code to visualise which boats carry whom \uD83D\uDE09)\n\nexample: \npeople =[3,2,2,1] limit=3, the boatlist has [ [3], [1, 2], [2] ] returning 3 boats. \n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nSorting takes O(N log N)\nTwo pointers traversing take O(N)\n\nso the overall TC is O(N log N) \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nConstant space.O(1)\n\n# Code\n```\nclass Solution:\n    def numRescueBoats(self, people: List[int], limit: int) -> int:\n        boats=0\n        boatlist=[]\n        l,r=0,len(people)-1\n        people.sort()\n        while l<=r:\n            #as long as heavier AND lighter person can fit\n            #maximize the number of people in each boat before considering single-person boats\n\n            if people[l]+people[r]<=limit:\n                boatlist.append([people[l],people[r]])\n                l+=1\n                r-=1\n            #if the limit exceeds, consider the heavier person alone\n            else:\n                boatlist.append([people[r]])\n                r-=1\n\n            boats+=1\n        print(boatlist)\n        return boats\n\n\n            \n```
['Two Pointers', 'Greedy', 'Sorting', 'Python', 'Python3']