# Java greedy algorithm with correctness proof, using PriorityQueue and waiting list

• The idea of greedy algorithm is at each time point we choose the task with most amount to be done and is also at least n apart from the last execution of the same task. Below is a proof of the correctness:

At some time, task A has the most remaining amount to be done and A is also at least n apart from its most recent execution. However, suppose the optimal solution doesn't choose A as the first task but rather chooses B. Assume we have x task A remain and y task B remain, we know x >= y.
Also assume in the optimal solution those m task A are done at a series of time points of a1, a2 ... ax, and n task B are done at a series of time points of b1, b2 ... by and we know that b1 < a1.
Further, we assume k is the largest number that for all i <= k, bi < ai. Now if we swap a1 and b1, a2 and b2 ... ak and bk, it will still be a valid solution since the separation between ak and ak+1 (if exists) becomes even larger. As to bk, it's the previous ak and bk+1 > ak+1 > ak(prev) + n = bk(now) + n.

So we proved that no solution will better than schedule A first.

Below is the code, I used priority queue to keep track of task with highest remaining amount. And a job can only enter the priority queue after n time points elapse from the previous execution of the same task which is achieved by a waiting list.

``````    public static int leastInterval(char[] tasks, int n) {
if(n == 0) return tasks.length;
int[] count = new int[26];
for (int t : tasks) count[t-'A']++;
PriorityQueue<int[]> maxheap = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o2[1] - o1[1];
}
});
for (int i = 0; i < 26; i++) {
if (count[i] > 0) maxheap.add(new int[]{i, count[i]});
}
int t = 0, waitCount = 0;
while (!maxheap.isEmpty() || waitCount > 0) {
t++;
int[] top = null;
if (!maxheap.isEmpty()) top = maxheap.poll();
if (top == null || --top[1] == 0) {
} else {
waitCount++;
}
if (waitlist.size() == n+1) {
int[] job = waitlist.poll();
if (job != null) {
waitCount--;
}
}
}
return t;
}
``````

• ``````            int[] job = waitlist.poll();
if (job != null) {
waitCount--;
}
``````

Hi，Thanks for sharing your code~ I'm kind of confusing about the code above, why you poll twice here. I'm looking forward to your reply. Much thx~

• @thsshxq Yes, I also have the same doubt... @dreamchase are you polling twice to keep the size of the linkedList always at n - 1?
Thanks!

• @dis_rain @dreamchase Also, I think because of this, it hits a null pointer exception case, when run against the test case: ['A','A','A','B','B','B'], with n = 2

I found most of your code and explanation really good and was able to understand, but could you please clarify this? Thanks

• @dis_rain I tried this myself

``````int [] job = waitlist.poll();
if(job != null){
waitCount--;
}
``````

I got AC. I think that poll twice is not OK.

• @thsshxq Yes, what you have written is correct.
Polling twice doesn't work

• Thanks, your answer not only gives the correct number, but also the right arrangement. This deserves more votes :)

• bk+1 > ak+1 > ak(prev) + n = bk(now) + n

Thanks for the prove of correctness! I'm just a little confused about why this equation proves that it's better to schedule A first, is it because bk+1 > ak+1 > ak(prev) + n = bk(now) + n > ak(now), so it satisfied the algorithm's idea to choose the task that at least n apart from the last execution?

• Great explanation！ Although it takes me 20 minutes to fully understand your proof and your code.

Since most users here are driven by the target of finding a job. I found that people sometimes rarely care about the proof. Thank you for your serious attitude.

• @younghobbits
I am also confused about the proof.
Why it's a better solution?
It only shows it is another valid solution.
If it shows that if we schedule A first, we could use smaller time to schedule all tasks, that makes sense. Otherwise it didn't.

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