881. Boats to Save People
Tags: ‘Two Pointers’, ‘Greedy’
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
Solution
public List<String> subdomainVisits(String[] cpdomains) {
Map<String, Integer> map = new HashMap<>();
for (String s: cpdomains) {
count(s, map);
}
List<String> result = new ArrayList<>();
for (String s: map.keySet()) {
result.add(String.valueOf(map.get(s)) + " " + s);
}
return result;
}
private void count(String s, Map<String, Integer> map) {
String[] split = s.split("\\s+");
int count = Integer.valueOf(split[0]);
String[] domains = split[1].split("\\.");
String curr = "";
for (int i = domains.length - 1; i >= 0; i--) {
curr = domains[i] + (i == domains.length - 1 ? "" : ".") + curr;
map.put(curr, map.getOrDefault(curr, 0) + count);
}
}