2024.5.14每日一题

admin2024-05-15  0

LeetCode

完成所有任务需要的最少轮数

题目链接:2244. 完成所有任务需要的最少轮数 - 力扣(LeetCode)

题目描述

给你一个下标从 0 开始的整数数组 tasks ,其中 tasks[i] 表示任务的难度级别。在每一轮中,你可以完成 2 个或者 3 个 相同难度级别 的任务。

返回完成所有任务需要的 最少 轮数,如果无法完成所有任务,返回 -1

示例 1:

输入:tasks = [2,2,3,3,2,4,4,4,4,4]
输出:4
解释:要想完成所有任务,一个可能的计划是:
- 第一轮,完成难度级别为 2 的 3 个任务。 
- 第二轮,完成难度级别为 3 的 2 个任务。 
- 第三轮,完成难度级别为 4 的 3 个任务。 
- 第四轮,完成难度级别为 4 的 2 个任务。 
可以证明,无法在少于 4 轮的情况下完成所有任务,所以答案为 4 。

示例 2:

输入:tasks = [2,3,3]
输出:-1
解释:难度级别为 2 的任务只有 1 个,但每一轮执行中,只能选择完成 2 个或者 3 个相同难度级别的任务。因此,无法完成所有任务,答案为 -1 。

提示:

  • 1 <= tasks.length <= 105
  • 1 <= tasks[i] <= 109

思路

贪心

代码

C++
class Solution {
public:
    int minimumRounds(vector<int>& tasks) {
        unordered_map<int, int> cnt;
        for (int t : tasks) {
            cnt[t]++;
        }
        int ans = 0;
        for (auto& [_, c] : cnt) {
            if (c == 1) {
                return -1;
            }
            ans += (c + 2) / 3;
        }
        return ans;
    }
};
Java
class Solution {
    public int minimumRounds(int[] tasks) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for(int t : tasks){
            cnt.merge(t,1,Integer::sum);
        }
        int ans = 0;
        for(int c : cnt.values()){
            if(c == 1){
                return -1;
            }
            ans += (c + 2) / 3;
        }
        return ans;
    }
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!