LeetCode 1665. 完成所有任务的最少初始能量

Categories:

题目描述
思路分析
1. 解法一：贪心排序（推荐）
相似题目

题目描述

✅ 1665. 完成所有任务的最少初始能量

思路分析

解法一：贪心排序（推荐）

核心思路：

每个任务有最低能量 minimum[i] 和消耗能量 actual[i]，完成任务需满足当前能量 >= minimum[i]

关键结论：对于两个任务 A、B，先做 A 再做 B 的条件 vs 先做 B 再做 A 的条件，推导排序规则

设先做 A 时需要 max(minA, minB + actualA)，先做 B 时需要 max(minB, minA + actualB)

推导得：若 minA - actualA < minB - actualB，则先做 A 更优，即按 minimum - actual 升序排序

排序后从头到尾贪心累加，维护所需最小初始能量

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示任务数量

空间复杂度：O(log n)，排序递归栈空间

class Solution {

  public int minimumEffort(int[][] tasks) {
    // 按 minimum - actual 升序排列
    Arrays.sort(tasks, (a, b) -> (a[0] - a[1]) - (b[0] - b[1]));

    int ans = 0;
    int cur = 0;

    for (int[] task : tasks) {
      int actual = task[1];
      int minimum = task[0];

      // 当前能量不足以开始该任务，需要补充
      if (cur < minimum) {
        ans += minimum - cur;
        cur = minimum;
      }

      // 完成任务，扣除消耗
      cur -= actual;
    }

    return ans;
  }
}

func minimumEffort(tasks [][]int) int {
    // 按 minimum - actual 升序排列
    sort.Slice(tasks, func(i, j int) bool {
        return tasks[i][0]-tasks[i][1] < tasks[j][0]-tasks[j][1]
    })

    ans, cur := 0, 0

    for _, task := range tasks {
        actual, minimum := task[1], task[0]

        // 当前能量不足，补充至 minimum
        if cur < minimum {
            ans += minimum - cur
            cur = minimum
        }

        // 完成任务
        cur -= actual
    }

    return ans
}

相似题目

题目	难度	考察点
1029. 两地调度	中等	贪心、排序
406. 根据身高重建队列	中等	贪心、排序
135. 分发糖果	困难	贪心
871. 最低加油次数	困难	贪心、堆
1353. 最多可以参加的会议数目	中等	贪心、堆
630. 课程表 III	困难	贪心、堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/37736577