Rearrange Tasks


  • 7
    H

    Given a set of tasks like [A, A, B], and int k, which is the waiting time between two same tasks. Calculate the min total execution time if you are allowed to rearrange the tasks. Assume the execution for each individual task is 1.

    In above example
    A A B, k = 1, without rearrangement, the execution time would be 4:

    A wait A B
    
    1  1   1 1
    

    with rearrangement, the execution time would be 3:

    A B A
    
    1 1 1
    

    Anyone has a good algorithm for this problem?


  • 8

    I guess this is a variation of this rearrange problem. Basically we need to put all the same tasks apart to avoid as much waiting time as possible.

    I would first count the frequency of each character, get the max count d and try to use that to rearrange the characters so that all the same characters become at least d distance away.

    If the input array is [A, A, A, B], in this case d is 3, first we get [A, '', '', A], since we still have a A left, the array becomes [A, A, '', A], finally, put B in the array and we get [A, A, B, A], so there's only one waiting time. Eventually go through the rearranged array and calculate the total time.

    Time complexity is O(n).

    I am not sure if that's the correct solution, but that's what I thought so far.


  • 0

    Yes, the idea is to count the frequency and it is a greedy algorithm. I have a very old post with the solution. Warning: my code could have bug as pointed in the comments.


  • 0

    Nice code! Thanks for sharing mate!


  • 0
    H

    Great! Thanks guys!


  • 7

    Here is my Java solution, actually I change the algorithm a little bit, after counting the frequency of each task, I sort them by their frequency, so we always try to handle the high-frequency task first (by using a max heap), so the time complexity becomes O(nlog(n)).

    Compared to @1337c0d3r's solution, it's a bit lengthy, hopefully it's easy for you to understand.

    Btw, the solution returns the new tasks, eventually we can go through the new tasks and calculate the total time.

    Example:

    input tasks: [A, A, A, A, C, D, E, E, B, B, B]

    output tasks: [A, B, E, D, A, B, E, C, A, B, A] (no waiting time)

    public class Solution {
      
      public char[] rearrangeTasks(char[] tasks) {
        int n = tasks.length;
        
        // step 1. go through the tasks and count the frequency
        Map<Character, Integer> map = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
          char task = tasks[i];
          map.put(task, map.containsKey(task) ? map.get(task) + 1 : 1);
        }
        
        // step 2. use a max heap to sort the tasks by frequency
        PriorityQueue<Task> heap = new PriorityQueue(new Comparator<Task>() {
          public int compare(Task a, Task b) {
            return b.frequency - a.frequency;
          }
        });
        
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
          heap.offer(new Task(entry.getKey(), entry.getValue()));
        }
        
        // step 3. organize the tasks and put them apart by d distance
        // d is the highest frequency
        int d = heap.peek().frequency;
        // let's reset the tasks
        tasks = new char[n];
        // the next empty slot
        int i = 0;
        
        while (!heap.isEmpty()) {
          Task task = heap.poll();
          
          // locate the next empty slot
          while (i < n && tasks[i] != '\0') i++;
          
          for (int j = i; j < n && task.frequency > 0; j += d) {
            tasks[j] = task.id;
            task.frequency--;
          }
          
          if (task.frequency > 0) {
            // this task is not done yet, put it back
            heap.offer(task);
          }
        }
        
        // finally return the rearranged tasks
        return tasks;
      }
      
      // helper class
      class Task {
        char id;
        int frequency;
        
        Task(char i, int f) {
          id = i;
          frequency = f;
        }
      }
      
    }
    

  • 0
    H

    I look through your program and I think the code is perfect!


  • 0
    S

    Thanks for sharing Jean!


  • 0

    What if the wait time = 2, and tasks = [A, A, B, B, C, C]? Seems like it will output [A, B, A, B, C, C], while the optimal rearrangement is [A, B, C, A, B, C].


  • 2

    You are right! I am not sure if this will work: step 1, count the characters, group them in a hash map and sort by the count; step 2, pick each character in count order and form the final string. This is a simple idea and it will solve the case above, but not sure if there's any corner case.


  • 2
    Z

    Main Idea :
    1st step:Create a min heap with the chars and their frequency. The min heap is ordered on the basis of the frequencies of the chars.
    2nd step: While the heap is not empty, do the following
    a. Pop elements from the min heap k times
    b.If the element popped is not null, append the char to the result string and push the task into a queue after decrementing the freq.
    If the popped element is null, append the string with "_" (indicates wait)
    c.After popping k elements from the minHeap, remove tasks from the queue and add them back to the heap if their freq is still > 0
    d.Print the result string [eg. AAB, k=1 will yield ABA | AAAB, k =1 will yield ABA_A]
    and return the length of the result string (which will be the min time required)

    Total running time
    nlogn (please correct if this is wrong!)

    	public String separateTasks(String taskSeq, int k) {
    		Map<Character,Integer> map = new HashMap<>();
    		for (char ch : taskSeq.toCharArray()){
    			if(!map.containsKey(ch))
    				map.put(ch, 1);
    			else
    				map.put(ch, map.get(ch)+1);
    		}
    		
    		class CompClass implements Comparator<Map.Entry<Character, Integer>>{
    			public int compare(Entry<Character, Integer> entry1, Entry<Character, Integer> entry2) {
    				if(entry2.getValue()==entry1.getValue()) //VERY IMPO:If the priority is the same, sort elements alphabetic order 
    					return entry2.getKey()-entry1.getKey();
    				else
    				return entry2.getValue()-entry1.getValue(); 
    			}
    		}
    		
    		CompClass comp = new CompClass();
    		PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(map.size(),comp);
    		maxHeap.addAll(map.entrySet());
    		
    		StringBuilder sb = new StringBuilder();
    		Queue<Map.Entry<Character, Integer>> queue = new LinkedList();
    		int remCharCount = taskSeq.length();
    		while(!maxHeap.isEmpty()) {
    			int count = k;
    			while(count>=0){
    				Map.Entry<Character, Integer> task = maxHeap.poll();
    				if(task!=null){
    					sb.append(task.getKey());
    					task.setValue(task.getValue()-1);
    					queue.offer(task);
    					remCharCount--;
    				}
    				else if (remCharCount>0){  //This is to avoid appending _ to the final string even if the whole task seq is processed, but k is remaining
    					sb.append("_");
    				}
    				
    				count--;
    			}
    			
    			int queSize = queue.size();
    			while(queSize!=0){
    				Map.Entry<Character, Integer> task = queue.poll();
    				if(task.getValue()>0)
    					maxHeap.offer(task);
    				queSize--;
    			}
    		}
    		System.out.println("Min length = "+sb.length());
    		return sb.toString();
    		
    	}
    

  • 0

    There seems to be a very easy O(n) solution from link text


  • 0
    N

    @yu6: The solution in the SO link is not clear. Try this example: AAABBBCCCDDDDDD, you will have DADADADBDBDBCCC.

    I think we have to build a max heap from the count. At each step i, if s[i-1] != heap.top we decrease heap.top to put into s[i], if s[i-1] == heap.top we decrease the second max (the greater child of heap.top) to put into s[i].

    Each decrease operation then update the heap sometimes only cost O(1) because each time we only decrease by 1. However, in the worst case where the branch contains all equal element it still cost O(logn). In conclusion, build max heap cost O(nlogn), build the final string s cost O(nlogn).

    With the above example, the result will be something like DADBDCDABCDABCD.


  • 4

    @namxh I agree the link is not very clear.
    Here is my solution based on the link.
    Assume k>0 and the goal is to minimize same characters next to each other.

    1. count the frequency of each character
    2. Put the max count character at index 0, 2, 4, ... i.
      If the end is reached (max_cnt>ceil(n/2)), wrap from back, For example, AAAB, we will have A_AA after this step. This minimizes same characters next to each other. Vacancies can be filled by other characters in any way because they are already seperated by the max_cnt character.
    3. If max_cnt <= ceil(n/2), it is possible to have 0 wait time. Schedule the next character at i+2, i+4,..., if the end is reached, wrap from the beginning.

    Time complexity is O(n).

    For your example AAABBBCCCDDDDDD
    schedule D first, D_D_D_D_D_D
    then A, DAD_D_D_D_D_A_A
    then B,C DADBDBDBDCDCACA


  • 0

    Approach: Setup a variable (w) to keep track of the total time that will be spent waiting.
    Count the number of times each task is repeated in the array, store these task counts in a list (counts). Count the total number of tasks (t).Iterate through task counts as
    long as t >= 1.For each task count that is greater than 1 (repeated task) do the following computation:
    waitingPeriods = count - 1 //Tells us the number of timeslots that will be spent waiting if the current similar tasks are arranged adjacent to one another.
    fillers = t - count //Tells us the number of tasks we have to fill up the waiting periods.
    If fillers < waitingPeriods, it means that some of the repeated tasks will end up beside one another in an optimal arrangement (adjacent = waitingPeriods - fillers). Otherwise,
    if fillers >= waitingPeriods then none of the repeated tasks will end up beside one another and hence adjacent = 0 as we won't spend anytime waiting. Update w with (w += (adjacent * k)).
    Discount the filler and optimally arranged tasks from t (t -= 2 * fillers) so that they will not be re-used to separate any future occurrences of repeated tasks.

    public int minTime(char[] c, int k){
    
    	List<Integer> ls = countRepeates(c);
    	int t = c.length;
    	int idx = 0;
    	int w = 0;
    	while(t > 1 && idx < ls.size()){
    		int waitingPeriods = ls.get(idx) - 1;
    		if(waitingPeriods > 0){
    			int fillers = t -= ls.get(idx);
    			if(fillers < waitingPeriods){
    				w  += (waitingPeriods - fillers)*k
    			}
    			t -= (2*fillers);
    			
    		}
    		idx ++;
    	}
    	return w + c.length;
    }
    
    
    
    
    public List<Integer> countRepeats(char[] arr){
    //Uses counting sort/bucket sort to count the number of repititons of each tasks and returns the counts as a list of integers.
    }
    

  • 0

    @1337c0d3r Actually I think the case you said is not a problem, because what you said wait time = 2 is actually wait time = d + 1, where d is the d in jeantimex's code. They are actually the same.


  • 0
    L

    I think we could use just ignore the rearrangement if k=0. For other cases, the characters could be added to a stack if the peek doesn't match with the character and then rest of the characters be added to stack at the end after repeating the same logic as above. Exceptions are when the search of the remaining array doesn't yield any duplicates. Not efficient than above solutions but a different perspective. Have a look.

    private static String rearrange(String str)
    {
      final Stack<Character> stack = new Stack<>();
      final List<Character> tasks = new LinkedList<Character>();
      for (final char c : str.toCharArray())
      {
        tasks.add(c);
      }
      Iterator<Character> it = tasks.iterator();
      final Set<Character> allItems = new HashSet<>();
      while (!tasks.isEmpty())
      {
        if (!it.hasNext())
        {
          final Set<Character> dups = tasks.stream()
              .filter(e -> !allItems.add(e))
              .collect(Collectors.toSet());
          if (dups.size() > 1)
          {
            it = tasks.iterator();
          }
          else
          {
            tasks.stream().forEach(e -> stack.push(e));
            tasks.clear();
            continue;
          }
        }
        final char c = it.next();
        if (stack.isEmpty() || (stack.peek() != c))
        {
          stack.push(c);
          it.remove();
        }
      }
      return stack.toString();
    }
    

  • 1
    T

    Below solution definitely works with O(NlogN) for small k:

    1. Create a map of (Character,Count)
    2. Create a priority queue(pq) sorted by count descending
    3. Pop elements from pq and store it in a buffer of size d.
    4. If buffer fills up, remove the first character, store it in the result array, decrement the count and add it back to the pq.
     static String rearrange(String input, int d) {
            //d = d-1;
            Map<Character,Integer> countMap = new HashMap<>() ;
            char[] str =  input.toCharArray();
    
            //Build a map of character and corresponding counts
            for(Character c : str)
                countMap.merge(c, 1, (integer, integer2) -> integer + integer2);
    
            //Sort by descending order of counts
            PriorityQueue<Map.Entry<Character,Integer>> pq = new PriorityQueue<>((a,b)->Integer.compare(b.getValue(),a.getValue()));
            countMap.entrySet().forEach(pq::add);
    
            LinkedList<Map.Entry> ll = new LinkedList<>();
            for(int i=0; i < str.length;){
                boolean processList = false;
                if(ll.size() < d) {
                    Map.Entry<Character, Integer> e = pq.poll();
                    if(e!=null) {
                        ll.addLast(e);
                    } else {
                        processList = true;
                    }
                } else {
                    processList = true;
                }
    
                if(processList) {
                    Map.Entry<Character, Integer> e = ll.removeFirst();
                    e.setValue(e.getValue()-1);
                    str[i] = e.getKey();
                    if(e.getValue() > 0)
                        pq.add(e);
                    i++;
                }
            }
    
            return new String(str);
        }

  • 1
    A
    private int minExecutionTime(char[] input, int k) {
        char[] aux = new char[26];
        int max = 0;
        for(char in : input) {
            aux[in-'A']++;
            if(aux[in-'A'] > max) {
                max = aux[in-'A'];
            }
        }
    
        int spots = (input.length+1)/2;
        int res = input.length;
        if(max > spots) {
            res += (max-spots)*k*2;
        }
    
        return res;
    }
    
    Time complexity: O(n)

Log in to reply
 

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