LeetCode -Task Scheduler

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.

However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Return the least number of units of times that the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

Example 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.

Example 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: 
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

Constraints:

• 1 <= task.length <= 104
• tasks[i] is upper-case English letter.
• The integer n is in the range [0, 100].

using System;
using System.Collections.Generic;
using System.Linq;

public class TaskScheduler
{
    public class task
    {
        public char name { get; set; }
        public int count { get; set; }
    }

    public int LeastInterval(char[] tasks, int n)
    {
        if (0 == n) return tasks.Length;

        Dictionary<char, int> counter = new Dictionary<char, int>();
        foreach (var task in tasks)
        {
            if (counter.ContainsKey(task))
            {
                counter[task]++;
            }
            else
            {
                counter.Add(task, 1);
            }
        }

        int chCount = 0, maxCount = 0, step = 0;
        foreach (var item in counter.Values)
        {
            if (item > maxCount)
            {
                chCount = 1;
                maxCount = item;
            }
            else if (item == maxCount)
            {
                chCount++;
            }
        }
       
        if (step >= tasks.Length) return step;
        return tasks.Length;
    }
}

using FluentAssertions;
using NUnit.Framework;

namespace TestProject1.TaskScheduler;

public class SolutionTests
{
    [SetUp]
    public void Setup()
    {
    }

    global::TaskScheduler _scheduler = new global::TaskScheduler();

    [Test]
    public void Test001()
    {
        var result = _scheduler.LeastInterval(new char[] {'A', 'A', 'A', 'B', 'B', 'B'}, 2);
        result.Should().Be(8);
    }    
    
    [Test]
    public void Test002()
    {
        var result = _scheduler.LeastInterval(new char[] {'A','A','A','B','B','B'}, 0);
        result.Should().Be(6);
    }
    
    [Test]
    public void Test003()
    {
        var result = _scheduler.LeastInterval(new char[] {'A','A','A','A','A','A','B','C','D','E','F','G'}, 2);
        result.Should().Be(16);
    }
}

step = (maxCount – 1) * (n + 1) + chCount;
公式這邊真的看無 ，看起來是找到最大重覆的task的次數後
實際推論上就是

例如new char[] {‘A’, ‘A’, ‘A’, ‘B’, ‘B’, ‘B’}, 2
那麼就是 A有3，B有3，n=2 那maxCount = 3, chCount = 2 (因為 > 0的時候 chcount就 =1，若有重覆次數的就再 +=1 )
所以step = (3-1)*(2+1) + 2 = 8

再假如new char[] {‘A’,’A’,’A’,’A’,’A’,’A’,’B’,’C’,’D’,’E’,’F’,’G’}, 2

那麼A有6，B~G各有1
那麼maxCount = 6
公式變成( 6-1) * (2+1)+1=16

照公式的概念就是，最多次數的task，肯定要被n次的限制卡住。若每一次的循環都要跑一次 A+?+?，代表 中間不論是塞次數少的的Task，若分配完了也是要塞 Idle Task。
那麼就代表至少要跑 6個就有5個區間，每個區間都至少要含自已是3個步驟。所以就是15次
那為啥chCount = 1。因為5個區間會少算最後一個出頭的Task。因為B~G總共也在 5次 ，剛好分配到5個區間中的間隔中，代表 塞完間隔後，因為次數不足，還要塞idle，才能再讓 次數最多的跑。