• 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?

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

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

• Nice code! Thanks for sharing mate!

• Great! Thanks guys!

• 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 {

// step 1. go through the tasks and count the frequency
Map<Character, Integer> map = new HashMap<>();

for (int i = 0; i < n; i++) {
}

// step 2. use a max heap to sort the tasks by frequency
return b.frequency - a.frequency;
}
});

for (Map.Entry<Character, Integer> entry : map.entrySet()) {
}

// step 3. organize the tasks and put them apart by d distance
// d is the highest frequency
int d = heap.peek().frequency;
// the next empty slot
int i = 0;

while (!heap.isEmpty()) {

// locate the next empty slot
while (i < n && tasks[i] != '\0') i++;

for (int j = i; j < n && task.frequency > 0; j += d) {
}

// this task is not done yet, put it back
}
}

// finally return the rearranged tasks
}

// helper class
char id;
int frequency;

id = i;
frequency = f;
}
}

}
``````

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

• Thanks for sharing Jean!

• 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]`.

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

• 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<>();
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);

StringBuilder sb = new StringBuilder();
Queue<Map.Entry<Character, Integer>> queue = new LinkedList();
while(!maxHeap.isEmpty()) {
int count = k;
while(count>=0){
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){
queSize--;
}
}
System.out.println("Min length = "+sb.length());
return sb.toString();

}
``````

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

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.

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

schedule D first, D_D_D_D_D_D

• 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.
}
``````

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

• 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<>();
for (final char c : str.toCharArray())
{
}
final Set<Character> allItems = new HashSet<>();
{
if (!it.hasNext())
{
.collect(Collectors.toSet());
if (dups.size() > 1)
{
}
else
{
continue;
}
}
final char c = it.next();
if (stack.isEmpty() || (stack.peek() != c))
{
stack.push(c);
it.remove();
}
}
return stack.toString();
}
``````

• 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()));

for(int i=0; i < str.length;){
boolean processList = false;
if(ll.size() < d) {
Map.Entry<Character, Integer> e = pq.poll();
if(e!=null) {
} 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)
i++;
}
}

return new String(str);
}``````

• ``````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)``````

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