881. 救生艇

救生艇

• 难度: medium
• 原始链接: https://leetcode.cn/problems/boats-to-save-people
• 标签: 贪心

解法一: 完全贪心

java

class Solution {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int n = people.length;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((num1, num2) -> num2 - num1);
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (!priorityQueue.isEmpty() && people[i] <= priorityQueue.peek()) {
                priorityQueue.poll();
            } else {
                ans++;
                priorityQueue.offer(limit - people[i]);
            }
        }
        return ans;
    }
}

解法二: 贪心

go

func numRescueBoats(people []int, limit int) int {
  sort.Ints(people)
  n := len(people)
  left := 0
  right := n - 1
  ans := 0
  for left <= right {
    if people[left]+people[right] <= limit {
      left++
    }
    right--
    ans++
  }
  return ans
}