/
BoatSavePeople.java
85 lines (72 loc) · 2.22 KB
/
BoatSavePeople.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
/*int[] res = {
method1(people, limit),
method2(people, limit),
method3(people, limit),
};*/
//System.out.println("New");
//System.out.println("Results = " + Arrays.toString(res));
//Arrays.sort(res);
return Math.min(
method1(people, limit),
Math.min(
method2(people, limit),
method3(people, limit)
)
);
}
// Method 1
// Try to put the lightest and the heaviest one at one go
int method1(int[] people, int limit) {
int count = 0, weight = 0, pCount = 0;
int l = 0, r = people.length - 1;
for (; l <= r; l++) {
if (weight + people[l] + people[r] <= limit) {
count++;
r--;
} else {
if (weight + people[l] <= limit && pCount == 0) {
weight += people[l];
pCount++;
} else {
count++;
weight = people[l];
pCount = 0;
}
}
}
return count + 1;
}
// Method 2
// Try to put as many light ones as possible
int method2(int[] people, int limit) {
int count = 0, weight = 0, pCount = 0;
for (int i = 0; i < people.length; i++) {
if (weight + people[i] <= limit && pCount == 0) {
weight += people[i];
pCount++;
} else {
count++;
weight = people[i];
pCount = 0;
}
}
return count + 1;
}
// Method 3
// Try to put a heavy person and then put 1 light one
int method3(int[] people, int limit) {
int count = 0, weight = 0;
int l = 0, r = people.length - 1;
for (; l <= r; r--) {
weight = people[r];
if (weight + people[l] <= limit) {
l++;
}
count++;
}
return count;
}
}