Skip to content

881. Boats to Save People 👍

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  int numRescueBoats(vector<int>& people, int limit) {
    int ans = 0;

    ranges::sort(people);

    for (int i = 0, j = people.size() - 1; i <= j; ++ans) {
      const int remain = limit - people[j--];
      if (people[i] <= remain)
        ++i;
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
  public int numRescueBoats(int[] people, int limit) {
    int ans = 0;

    Arrays.sort(people);

    for (int i = 0, j = people.length - 1; i <= j; ++ans) {
      final int remain = limit - people[j--];
      if (people[i] <= remain)
        ++i;
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def numRescueBoats(self, people: list[int], limit: int) -> int:
    ans = 0
    i = 0
    j = len(people) - 1

    people.sort()

    while i <= j:
      remain = limit - people[j]
      j -= 1
      if people[i] <= remain:
        i += 1
      ans += 1

    return ans