Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Boats to Save People
- https://leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/580/week-2-january-8th-january-14th/3602/
- 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
- */
- /*
- each boat can carry 2 Perons atmost , so try to pair with heavy and light person
- */
- class Solution {
- public:
- int numRescueBoats(vector<int>& people, int limit) {
- std::sort(people.begin(), people.end());
- int boats = 0;
- int start = 0, end = people.size() - 1;
- while(start <= end) {
- boats++;
- if(people[start] + people[end] <= limit)
- start++;
- end--;
- }
- return boats;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement