😎 C++ Greedy 100% n log n - Easy to Understand
Greedy Two Pointers [Accepted]\n\n## Intuition\nFrom the start, it seems like a combinatorial problem where we have to perhaps form different pairs. But the key
# Greedy Two Pointers [Accepted]\n\n## Intuition\nFrom the start, it seems like a combinatorial problem where we have to perhaps form different pairs. But the key observation is that we can put in **at most** two people into a boat, as long as `people[i] + people[j] <= limit`. In order to do this efficiently, we can simply attempt to pair the lightest person with the heaviest person.\n\nOur main intuition therefore is: the current heaviest person will take a boat. But we will fit the current lightest person if it\'s possible.\n\n## Algorithm Design\n- Sort the `people` array.\n- Perform two pointers from each end\n    - Move the light person pointer if we can fit that person into the boat\n    - Increment boat count.\n\n## Code\n```cpp\nclass Solution {\npublic:\n    int numRescueBoats(vector<int>& people, int limit) {\n        int boats = 0;\n\n        // Sort people in ascending order\n        sort(people.begin(), people.end()); // O(n log n)\n        \n        // Two Pointer from two ends. \n        // lightPtr is the current lightest person\n        // heavyPtr is the current heaviest person\n        int lightPtr = 0;\n        for(int heavyPtr = people.size() - 1; heavyPtr >= 0 && lightPtr <= heavyPtr; heavyPtr--) { // O(n)\n            // Put in the current lightest person if possible\n            if(people[lightPtr] + people[heavyPtr] <= limit) lightPtr++;\n            \n            // Increment number of boats\n            boats++;\n        }\n\n        return boats;\n    }\n};\n```\n\n## Complexity\nLet\'s define `n` as the length of `people`.\n\n- Time Complexity: $$O(n log n)$$\n- Space Complexity: $$O(1)$$\n  - Sorting in C++ takes $$O(log n)$$ space.
['Two Pointers', 'Greedy', 'Sorting', 'C++']