Minimal run time scheduler

  • 2

    Given a task sequence tasks such as ABBABBC, and an integer k, which is the cool down time between two same tasks. Assume the execution for each individual task is 1 unit.

    For example, if k = 3, then tasks BB takes a total of 5 unit time to finish, because B takes 1 unit of time to execute, then wait for 3 unit, and execute the second B again for another unit of time. So 1 + 3 + 1 = 5.

    Given a task sequence and the cool down time, return the total execution time.

    Follow up: Given a task sequence and the cool down time, rearrange the task sequence such that the execution time is minimal.

  • 0

    I think that the follow up of the problem is very common to the problem will try greedy to arrange tasks with distance case this doesn't work, we will not return "no possible arrangement",but we will put the same tasks one to another

  • 0

    @elmirap Good observation. Yes it is a variation of the other problem.

  • 0

    Can we not look at it as something like an interleaving iterator? Let's say the task counts are as follows:

    We can simply do an interleaving as follows:

    Returning an interleaved version with round robin interleaving would minimize the cases with a task following itself.

  • 0

    @elmirap said in Minimal run time scheduler:

    What about use a priority queue, with the frequency of each task being the comparison key and we dynamically pick the most, second most letter (thus update the frequency therefore the priority queue)? In this way we always greedily pick the most abundant tasks alternatively.

  • 0

    can't we just use a map<char,int> where we loop threw the array if the character is not in the map add it and the index it occured at
    if it is in the map we now have two possibilities. one the cooldown time has passed and we just add one or two the we subtract the current index - the occurance in the map add one and add that to our sum total.

  • 0

  • 0

    @diptesh This is not correct. I just give one example. Task AAABC. The cooldown is 1. In your solution, the sequence will be ABCA_A. But the optimum one is ABACA.


Log in to reply