# Java PriorityQueue solution - Similar problem Rearrange string K distance apart

• The idea used here is similar to - https://leetcode.com/problems/rearrange-string-k-distance-apart
We need to arrange the characters in string such that each same character is K distance apart, where distance in this problems is time b/w two similar task execution.

Idea is to add them to a priority Q and sort based on the highest frequency.
And pick the task in each round of 'n' with highest frequency. As you pick the task, decrease the frequency, and put them back after the round.

``````public int leastInterval(char[] tasks, int n) {
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < tasks.length; i++) {
map.put(tasks[i], map.getOrDefault(tasks[i], 0) + 1); // map key is TaskName, and value is number of times to be executed.
}
PriorityQueue<Map.Entry<Character, Integer>> q = new PriorityQueue<>( //frequency sort
(a,b) -> a.getValue() != b.getValue() ? b.getValue() - a.getValue() : a.getKey() - b.getKey());

int count = 0;
while (!q.isEmpty()) {
int k = n + 1;
List<Map.Entry> tempList = new ArrayList<>();
while (k > 0 && !q.isEmpty()) {
Map.Entry<Character, Integer> top = q.poll(); // most frequency task
top.setValue(top.getValue() - 1); // decrease frequency, meaning it got executed
k--;
count++; //successfully executed task
}

for (Map.Entry<Character, Integer> e : tempList) {
}

if (q.isEmpty()) break;
count = count + k; // if k > 0, then it means we need to be idle
}
return count;
}``````

• Is there a proof why this greedy approach works?

• @macrohard I'm not good with proofs, but it boils down to few factors.

The goal is to use least number of intervals.

So, lets say we have AAAAA BBB CCC DD and n = 2
Independently, just execution of A, B, C and D looks like this.
`A - idle - idle - A - idle - idle - A - idle - idle - A - idle - idle - A`
`B - idle - idle - B - idle - idle - B`
`C - idle - idle - C - idle - idle - C`
`D - idle - idle - D`

As you can see, the execution actually becomes a cycle of 3 tasks. Meaning, the task execution should have 3 unique tasks in a sequence. This uniqueness is critical for this problem. The goal is, for each cycle you need make a choice among tasks in such a way that for the next cycle you still have enough unique tasks.

Why? Lets say,
To start with, you have 4 unique tasks, ABC and D. Lets say your execution is `B-C-D-B-C-D`, which is a valid case, BUT you used up all `D`. Now for the remaining execution, you have only 3 unique tasks. Then you'll pick `-B-C-A-`. You used up all B and C, and remaining 4 A's, which has to be executed with idle times.

But if instead of choosing D, if you had picked the A at first, by the time you finish executing all B and C, you would still have 2 unique tasks A and D, whihc further reduces idle times. So instead of `B-C-D`, starting with `A-B-C` will ensure that, by the time B and C are used up, we still have 2 tasks to reduce idle times.
Also, note that if you start with `ABC` instead of `BCA` it can further optimize to use A immediately.

• I came up almost the same idea and I have not figured out why this greedy works but from the intuition, distinct characters will construct a period with length `n` and the rest of them will pair with `idle`.

• Same idea, different implementation:

``````public int leastInterval(char[] tasks, int n) {

int[] frequencies = new int[26];
for (char c : tasks) frequencies[c - 'A']++;

Queue<Integer> pq = new PriorityQueue<>((a,b) -> b-a);
for (int i : frequencies) if (i != 0) pq.add(i);

Map<Integer, Integer> map = new HashMap<>();
int time = 0, tasksRemaining = tasks.length;
while (tasksRemaining > 0) {
Integer prev = map.get(time);
if (prev != null) pq.add(prev);
Integer cur = pq.poll();
if (cur != null) tasksRemaining--;
if (cur != null && --cur > 0) map.put(time + n + 1, cur);
time++;
}
return time;

}
``````

• @macrohard Hey, when I saw the solution, I had the same doubt, specially because of the below line.

``````    while (k > 0 && !q.isEmpty()) {
Map.Entry<Character, Integer> top = q.poll(); // most frequency task
top.setValue(top.getValue() - 1); // decrease frequency, meaning it got executed
k--;
count++; //successfully executed task
}
``````

As, k is counter for only first popped value. How will it remember if second or futher poped value's cooling time n has reached.

But, as per my understanding, this solution works because of "properties of sort"

Example -> AAAABBBCCDDD,
Loop 1 -> A(4), B(3), D(3), C(2) n=3 => ABDC
....................value of k in inner while => 43 21

Loop 2 -> A(3), B(2), D(2), C(1) n=3 => ABDC
....................value of k in inner while => 43 21
// As we can see, B won't come back A and D won't come before B, because of lexiographic order we put it in tempList and add in the same order back
// so if A is cool downed, B,D and C should could down in 1, 2 and 3 steps respectively.
// And as per first comment, that is the 'minimum' step required before we can use each of them.

Loop 3 -> A(2), B(1), D(1), C(0) n=3 => ABD_
....................value of k in inner while => 43 21

Loop 4 -> A(1), B(0), D(0), C(0) n=3 => A // q is empty // breaks both while
....................value of k in inner while => 4

As, shown on comments after Loop 2, because of lexiographic order, we do make sure any char, which has counter > 0, gets selected only after n cool downs.

• @siddharthlc aaaa thank you!!!!!

• @compton_scatter Hi I am really interested in your code, but I have some problems in understanding the while loop. Can you explain a little more about what's the basic idea behind the while loop?

And to be more specific, what do the two fields of map represent? I have trouble in understanding map.put(time + n + 1, cur).

Thank you very much!

• `(a,b) -> a.getValue() != b.getValue()`
should be
`(a,b) -> !a.getValue().equals(b.getValue())`
You are comparing two Integer objects

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