Explaining intuitive thoughts and self explanatory code
Intuition\nIf we boil down the problem statement , we are given limit of a boat i.e. maximum weight(it can be sum of weight of 2 people or weight of a single pe
# Intuition\nIf we boil down the problem statement , we are given limit of a boat i.e. maximum weight(it can be sum of weight of 2 people or weight of a single person) it can carry. Now we need to tell how many boats are needed to carry people . Till now we can say maximum number of boats needed to carry n people will be n boats(1 person per boats) . But question ask us to minimize the number of boats. So we will arrange people according to their weights and find out those pairs whose sum of wieghts is below limit. We will do this until no such pair is left after that boat will carry only one persons(applied for all remaining peoople).\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nNow we just need to find out a way to send pairs.What we will do we will pick least weighted person first and pair him with most weighted person(provided sum of their weights is less than limit) . Here you can argue with me on some points.\n --> Why not we make pair of least weight people only or most weighted people first.\n\nAnswer to that statement is that we neeed to minimize the number of boats.\n\n\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n$$O(nlong(n))$$ \n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int numRescueBoats(int[] people, int limit) {\n        Arrays.sort(people);\n\n        int start = 0;\n        int last = people.length-1;\n        int ans = 0;\n\n        while(start < last){\n            int sum = people[start] + people[last];\n// candition when we found a pair\n            if(sum <= limit)\n            {\n                ans++;\n                start++;\n                last--;\n            }\n// if we didnt find a pair we need to minimize the larger weight and we can only minimize the larger weight since we are paining least weight person with most compatible weighted person\n            else{\n                last--;\n            }\n           \n        }\n// ans stores number of pairs so ans * 2 = number of people already boarded\n        int count = ans * 2;\n// ans =(number of people - number of people already boarded) + number of pairs\n        ans += people.length - count;\n        return ans;\n        \n        \n        \n    }\n}\n```
['Two Pointers', 'Greedy', 'Sorting', 'Java']