|
| 1 | +/** |
| 2 | + * The i-th person has weight people[i], and each boat can carry a maximum |
| 3 | + * weight of limit. |
| 4 | + * |
| 5 | + * Each boat carries at most 2 people at the same time, provided the sum of the |
| 6 | + * weight of those people is at most limit. |
| 7 | + * |
| 8 | + * Return the minimum number of boats to carry every given person. |
| 9 | + * (It is guaranteed each person can be carried by a boat.) |
| 10 | + * |
| 11 | + * Example 1: |
| 12 | + * Input: people = [1,2], limit = 3 |
| 13 | + * Output: 1 |
| 14 | + * Explanation: 1 boat (1, 2) |
| 15 | + * |
| 16 | + * Example 2: |
| 17 | + * Input: people = [3,2,2,1], limit = 3 |
| 18 | + * Output: 3 |
| 19 | + * Explanation: 3 boats (1, 2), (2) and (3) |
| 20 | + * |
| 21 | + * Example 3: |
| 22 | + * Input: people = [3,5,3,4], limit = 5 |
| 23 | + * Output: 4 |
| 24 | + * Explanation: 4 boats (3), (3), (4), (5) |
| 25 | + * |
| 26 | + * Note: |
| 27 | + * 1 <= people.length <= 50000 |
| 28 | + * 1 <= people[i] <= limit <= 30000 |
| 29 | + */ |
| 30 | + |
| 31 | +publicclassBoatsToSavePeople885 { |
| 32 | +publicintnumRescueBoats(int[]people,intlimit) { |
| 33 | +Arrays.sort(people); |
| 34 | +intres =0; |
| 35 | +intN =people.length; |
| 36 | +inti =0; |
| 37 | +intj =N-1; |
| 38 | +while (i <j) { |
| 39 | +if (people[i] +people[j] >limit) { |
| 40 | +j--; |
| 41 | + }else { |
| 42 | +i++; |
| 43 | +j--; |
| 44 | + } |
| 45 | +res++; |
| 46 | + } |
| 47 | +if (i ==j)res++; |
| 48 | +returnres; |
| 49 | + } |
| 50 | + |
| 51 | +} |