Is there a faster solution for the Google Code Jam Great Wall Problem
The obvious room for improvement is this step:


  Generates all the Attacks every Tribe will perform, and sorts them by day - $O(A\log A)$


We know that the tribes will attack from a particular day, in regular intervals. That means we should be essentially merging lots of pre-sorted lists. Also the problem statement tells us that there will never be more than 1,000 tribes (i.e. 1,000 lists to merge); a tiny number compared with the 1,000,000 maximum attacks! Depending on your implementation's relative timings, switching this could cut the processing time in half.

That's really all I can suggest for optimising the theoretical complexity, but I have no proof that it would be optimal after this change.



I gave the puzzle a go myself, but I used a much dumber representation of the wall: a binary search tree (C++'s std::map to be precise) storing locations where the wall's height changes. With this, I was able to add and removed nodes as required (i.e. if a complicated section was subject to a large, overwhelming attack, or multiple attacks of the same strength touched, the number of nodes would reduce significantly). This solved the large input in 3.9 seconds (on my mid-spec development laptop). I suspect there are several reasons for the improvement:


As you pointed out, boxing and unboxing can get expensive, but C++'s template-based containers avoid this entirely.
While the wall representation I used is theoretically worse, in the vast majority of cases being able to dynamically reduce the number of nodes made it super-fast (most test cases maxed-out at under 1k nodes, and all but 2 were under 10k). In fact, the only case which took any significant time was #7, which seems to have been testing lots of non-intersecting ranges.
I used no pre-processing (stages are determined by keeping track of when each tribe will next attack, and searching for the joint-lowest each turn). Again this is theoretically worse, but for the majority of cases I suspect the lower overhead means it was faster (I'll test this and get back to you). Update: I added a priority queue for attacks, similar to the method described above (although instead of creating the large array I calculated it on-the-fly) and saw the time decrease to 3.0 seconds for the large input.


In short, while I think your algorithm is near-optimal in the general case, there are several ways you could speed it up for typical inputs.