Leetcode-621-タスクスケジューラ(java)



Leetcode 621 Task Scheduler



トピックとテスト

package pid621 /* Task Scheduler Given a list of tasks that the CPU needs to perform, represented by an array of characters. It contains 26 different kinds of tasks represented by uppercase A-Z letters. Tasks can be executed in any order, and each task can be executed in 1 unit time. The CPU can perform a task in any unit time, or in a standby state. However, there must be a cooling time of length n between two tasks of the same kind, so the CPU is performing different tasks for at least n consecutive units of time, or is in a standby state. You need to calculate the minimum amount of time required to complete all tasks. Example 1: Enter: tasks = ['A','A','A','B','B','B'], n = 2 Output: 8 Execution order: A -> B -> (standby) -> A -> B -> (standby) -> A -> B. Note: The total number of tasks is [1, 10000]. The value of n ranges from [0, 100]. */ import java.util.List public class main { public static void main(String[] args) { char [][] testTable = {{'A','A','A','B','B','B'},{'A','A','C','B','B','B'}} int [] testTable2 = {2,1} for(int i=0i

考えなかった



解決策1(その他)

この例から、タスクスケジューリングのルールを取得できます。
与えられたように:AAABBCD、n = 2。次に、必要な数のタスクを満たすことができます。これにより、タスク間隔の要件を満たすことができます。つまり、AXXAXXA(Xは、タスクを満たすために必要な間隔またはアイドル状態を示します)
AAAABBBBCCDE、n = 3のように、タスクの最大数が同じであるタスクが2つ以上ある場合。次に、同じ数のタスクAとBをタスクペアと見なし、最後に必要な割り当てはABXXABXXABXXABです。残りのタスクは、必要な間隔に違反することなく間隔に挿入でき、空席位置はアイドルを補完します。
上記の分析から、必要な最小タスク時間は次のようになります。(最大タスク数-1)*(n + 1)+(同じ最大タスク数を持つタスク数)。
上記の例では:(num(A)-1)*(3 + 1)+(2)。



ただし、間隔が小さすぎて、最大タスクを実行した後、他のタスクはまだ実行されていない場合があります。少なくともタスクの総数は秒であるため、タスクの総数と合計します。

class Solution { public int leastInterval(char[] tasks, int n) { int[] count = new int[26] / / First calculate the frequency of all subtitles appear for (int i = 0 i = 0 && count[25] == count[index]){ index-- } / / There is a case where the minimum value is the length of the array return Math.max((count[25] - 1) * (n + 1) + 25 - index, tasks.length) }