LeetCode101: 881. Boats to Save People

class Solution {
public:
	int numRescueBoats(vector<int>& people, int limit) {
		unordered_map<int, int> cntOfWeights;
		for (auto iter = people.begin(); iter != people.end(); ++iter) {
			cntOfWeights[*iter]++;
		}
		int r = 0;
		for (int i = 0; i < people.size(); i++) {
			if (cntOfWeights[people[i]] == 0) {
				continue;
			}
			cntOfWeights[people[i]]--;
			for (int j = (limit - people[i]); j > 0; --j) {
				if (cntOfWeights.find(j) != cntOfWeights.end() && cntOfWeights[j] > 0) {
					cntOfWeights[j]--;
					break;
				}
			}
			r++;
		}
		return r;
	}
};

class Solution {
public:
	int numRescueBoats(vector<int>& people, int limit) {
		int i = 0;
		int j = people.size() - 1;

		// heaviest go first
		sort(people.rbegin(), people.rend());

		for (; i <= j; i++) {
			if (people[i] + people[j] <= limit)
				j--;
		}
		return i;
	}
};