leetcode
leetcode 1951 ~ 2000
完成所有任务需要的最少轮数

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

难度:

标签:

题目描述

代码结果

运行时间: 81 ms, 内存: 30.9 MB


/*
 * Solution using Java Stream API
 * 
 * This approach uses the same logic as the standard Java solution but leverages Java Streams to handle
 * the collection and counting of task frequencies.
 */
import java.util.Arrays;
import java.util.Map;
import java.util.stream.Collectors;

public class TaskSchedulerStream {
    public int minRounds(int[] tasks) {
        // Count the frequency of each difficulty level using Streams
        Map<Integer, Long> frequencyMap = Arrays.stream(tasks)
                .boxed()
                .collect(Collectors.groupingBy(task -> task, Collectors.counting()));
        // Calculate the minimum rounds needed
        int rounds = 0;
        for (long freq : frequencyMap.values()) {
            if (freq == 1) {
                return -1; // Impossible to complete
            }
            rounds += (freq + 2) / 3; // Minimum rounds needed to cover freq tasks
        }
        return rounds;
    }
}

解释

方法:

该题解首先使用计数器统计每个任务难度出现的次数。然后遍历这些计数,针对每个计数,判断是否为1,因为一个任务无法在一个轮次内完成(要求每轮完成2或3个相同任务)。如果某个任务的数量为1,则直接返回-1,表示无法完成所有任务。否则,计算完成这种难度任务所需的最少轮数,利用数学技巧(c+2)//3得到向上取整的结果,即在每轮尽可能完成3个任务,然后计算总轮数。最后,返回所有任务所需的总轮数。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在算法中,如何处理当任务数量正好为2的情况,是否直接计算为1轮,还是有特别的处理方式?
在算法中,当任务数量正好为2时,直接计算为1轮。这是因为题目规定每轮可以完成2或3个相同的任务。因此,如果任务数量正好为2,可以在一轮中完成这两个任务,无需特别的处理方式。
🦆
题解中提到利用数学技巧`(c+2)//3`来计算最小轮数,请问这个公式是如何推导出来的,它如何确保能够覆盖所有情况且不会产生多余的轮数?
这个公式`(c+2)//3`是一种向上取整的计算方法,用于计算至少需要多少轮可以完成`c`个任务。当`c % 3 == 0`时,正好每轮完成3个任务;`c % 3 == 1`时,会有一轮只能完成一个任务,这不符合题目要求,因此通过添加2个假想的任务,使其能被3整除,从而计算轮数;`c % 3 == 2`时,正好有一轮完成2个任务。这种计算方式确保了不管任务数如何,都能通过尽可能多地每轮完成3个任务来最小化轮数,而添加的2只是为了使整除3时计算方便,并不会影响实际轮数的计算。
🦆
对于难度级别相同的任务数量`c`大于或等于3的情况,是否考虑了不同的组合方式可能导致轮数的变化?例如,5个任务可以是2轮(3+2)还是仅按此公式计算?
在这个题解中,我们使用的`(c+2)//3`公式已经考虑了最优的组合方式。对于5个任务的例子,按照公式计算为`(5+2)//3 = 7//3 = 2`轮,这符合3个任务一轮和2个任务一轮的最优组合(3+2)。因此,该公式已经自然地考虑了不同的组合方式,以确保总轮数是最小的。
🦆
当存在多种难度的任务时,题解是否考虑了不同难度任务之间的依赖或影响,比如某种方式的组合可能会减少总轮数?
题解中每种难度的任务是独立处理的,没有考虑不同难度任务之间的依赖或相互影响。因为每轮只能完成相同难度的任务,所以不同难度的任务无法在一轮中组合。每种难度的任务都按其数量单独计算所需的最少轮数,然后将这些轮数相加得到完成所有任务的总轮数。这保证了计算的简洁性和正确性。

相关问题