给你一个下标从 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 <= 10^5$
$1 <= tasks[i] <= 10^9$
首先分析一下,只能每轮完成2个或者3个,那么要求轮次最小,那么肯定贪心的想我们肯定优先完成3个任务,那么就有三种情况
- 最后剩0个:就是直接每轮完成3个,这个是最优的。不用再考虑每轮完成两个的情况。
- 最后剩一个:剩一个的话我们就需要再向同类之前3个分一个,也就是从3,1变成2,2这样就能够完整的完成任务。但是如果这类任务只有一个,则无法完成
- 最后剩两个,剩两个我们直接完成这两个任务即可。
func minimumRounds(tasks []int) int {
l:=len(tasks)
mp:=map[int]int{
}
for i:=0;i<l;i++{
mp[tasks[i]]++
}
ans:=0
for _,value:=range mp{
//fmt.Println(a,value)
if value==1{
return -1
}
s:=value%3
if s==0{
ans+=value/3
}else {
ans+=value/3+1
}
}
return ans
}