Java – why is this code applicable to this TopCoder problem?

I've been trying to think about this TopCoder problem from hours, and I can't find a perfect solution, and I find that the one given below is crazy!

I want to find out how this solution applies to a given detector? How could I have thought of it? After reading the solution, I think it is a variant of Hoffman coding, but this is what I can get I'm really fascinated and want to know what ideas can lead to this solution

This is the problem: http://community.topcoder.com/stat?c=problem_statement&pm=11860&rd=15091

This is the solution I found in link

import java.util.*; 

public class FoxAndDoraemon { 
  public int minTime(int[] workCost,int splitCost) { 
    PriorityQueue<Integer> pq = new PriorityQueue<Integer>(); 

    for(int i : workCost) pq.offer(i); 

    while(pq.size()>=2) { 
      int i = pq.poll(); 
      int j = pq.poll(); 
      pq.offer(Math.max(i,j) + splitCost); 
    } 
    return pq.poll(); 

  } 
}

Solution

First, you will realize the reasons behind 'max (I, J) splitcost' isn't it? Basically, if you have a fox, you divide it into two and complete each task independently Let's call this process "consolidation"

Now suppose we have three jobs a, B and C, so that a > b > C. you can merge (merge (a, b), c) or merge (merge (a, c), b) or merge (merge (B, a) By calculation, you can prove that merge (B, a) is the least of the three

You can now use induction to prove that this solution is applicable to any number of jobs (not just 3)