20 Dec 2015
At first, I was thinking that either min salary or max salary should be removed in order to reduce the difference. That sounds easy enough. But finding min/max and removing a node (with its children) seems to consume a lot of time.
It turns out that we can just find possible ranges. For example, we cannot remove root. Therefore, the min/max must be in the range of m0's salary +- D. It gets easier if we say all the salaries should be in the range [X - D, X]. From m0's salary, the range for X is [s0, s0 + D]. Then, we do that for every node.
One thing to note is that the range of a child node should be within the range of its parent node because, if the parent is removed, the child is removed as well.
If a child's range does not intersect with its parent's range at all, then we definitely have to remove the child.
Since we have all the possible ranges from all nodes, we need to find a value V that will fall into the most number of ranges. We can find V by:
Now we want to find the maximum number of intervals that overlap at any point. Let the interval we get for employee i be [Ai, Bi]. Create an array of pairs of integers, with two pairs for each employee: one containing (Ai, +1) and the other containing (Bi, -1). Sort this array by the first numbers of the pairs, breaking ties using the second number, by putting entries with +1 before those with -1. Then we start a counter at zero, and iterate through the array in sorted order. Add the second number of each pair to the counter. The maximum value of the counter is the answer to the problem.
It took me a while to understand why it works…