Minimal run time scheduler


  • 4
    Q

    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 https://discuss.leetcode.com/topic/102/rearrange-string.We will try greedy to arrange tasks with distance 2.in 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.


  • 1
    D

    Can we not look at it as something like an interleaving iterator? Let's say the task counts are as follows:
    A-3
    B-5
    C-2

    We can simply do an interleaving as follows:
    BACBACBABB

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


  • 1
    J

    @elmirap said in Minimal run time scheduler:

    https://discuss.leetcode.com/topic/102/rearrange-string.We

    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.


  • 1
    N

    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

  • 2
    T

    @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.

    Towhid


  • 0
    P

    what is the solution for the first part (not the followup)


  • 0
    O
    This post is deleted!

  • 0
    R

    @Okma this is wrong. Your code only keeps track of the last task, and only waits for cooldown if the last task is the same as the new one.
    For example with the input: ABA with K=5, the correct answer is 7, because after completing B we still have to wait 4 more time units before we can start A again. But your code returns 3 because the if condition is never true.
    A correct solution would be to keep for each task the last time this task started, so when this task has to start again we can wait for (full or partial) cooldown. If tasks are known to be called A-Z just keep this in an array. If the string is unicode, keep a map/dictionary.


  • 0
    E
    This post is deleted!

  • 0
    L

    See my implementation for this issue below. Given tasks = "ABBABBC" and k = 3, it returns 13.

       public int getExecutionTime(String tasks, int k) {
            if (tasks == null || tasks.length() == 0 || k < 0) {
                return 0;
            }
            char curr;
            char pre = tasks.charAt(0);
            int count = 1;
            for (int i = 1; i < tasks.length(); i++) {
                curr = tasks.charAt(i);
                if (curr == pre) {
                    count += k;
                }
                count += 1;
                pre = curr;
            }
            return count;
        }
    

  • 0
    O

    @ran Yes, you're right. I misinterpreted the question prompt.


  • 0
    S

    I think we can directly reuse the code from Rearrange String k Distance Apart.
    I modify this from another thread, here.

    # Q1
    def getExecutionTime(task, k):
        count = 0
        for idx, t in enumerate(task):
            if idx + 1 < len(task) and task[idx] == task[idx + 1]:
                count += k
        return count + len(task)
    
    print getExecutionTime("ABBABBC", 3)
    print getExecutionTime("BB", 3)
    
    
    # Follow up
    import collections
    import heapq
    
    def rearrangeString(s, k):
    
            if k == 0:
                return s
            # max heap
            h = [(-freq, ch) for (ch, freq) in collections.Counter(s).items()]
            heapq.heapify(h)
            res = []
            k += 1
            while len(res) < len(s):
                q = []
                for _ in range(k):
                    # for some case, we can reach len(s) without k, for example, "a" 2, we driectly get len(res) == len(s)
                    # also, for AAABBBBBCC, we should stop ASAP
                    if len(res) == len(s):
                        return ''.join(res)
                    if len(h) > 0:
                        freq, ch = heapq.heappop(h)
                        res.append(ch)
                    if freq < -1:
                        q.append((freq + 1, ch))
                while q:
                    heapq.heappush(h, q.pop())
            return ''.join(res)
    
    print  rearrangeString('AAABC', 1)
    print rearrangeString('AAABBBBBCC', 2)
    print rearrangeString('A',2)
    
    

  • 0
    K

    i think this question is now available on leetcode https://leetcode.com/problems/task-scheduler/description/


  • 0
    F

    @salamanderrex I think there is a problem here. What if the task is 'ABAB' and k = 4?

    In this case, the result will be A _ _ BA _ _B


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.