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


  • 11

    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]});
            }
            LinkedList<int[]> waitlist = new LinkedList<>();
            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) {
                    waitlist.add(null);
                } else {
                    waitlist.add(top);
                    waitCount++;
                }
                if (waitlist.size() == n+1) {
                    int[] job = waitlist.poll();
                    if (job != null) {
                        maxheap.add(waitlist.poll());
                        waitCount--;
                    }
                }
            }
            return t;
        }
    

  • 0
    T

    @dreamchase said in Java greedy algorithm with correctness proof, using PriorityQueue and waiting list:

                int[] job = waitlist.poll();
                if (job != null) {
                    maxheap.add(waitlist.poll());
                    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~


  • 0
    D

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


  • 0
    D

    @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


  • 1
    T

    @dis_rain I tried this myself

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

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


  • 0
    D

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


  • 0

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


  • 0

    @dreamchase said in Java greedy algorithm with correctness proof, using PriorityQueue and waiting list:

    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?


  • 0
    I

    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.


  • 0
    L

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


Log in to reply
 

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