If all of the customer requests were of the same amount of frequency,
this problem reduces to coloring an interval graph.
Such colorings can be found in time by sorting the intervals
and assigning colors from left to right.
The chromatic number is defined by the maximum number of intervals which
can be stabbed by one point.
This interval graph coloring algorithm provides for an immediate r-factor
approximation, where r is the ratio of the largest to smallest frequency
request.
Simply ignore the weights, and treat it as an interval graph.
Muthu and I (prior to reading group) had used this idea to get an
factor approximation by partitioning the weights into bins by approximate size,
and solving each bin independently.
Muthu and Mike Paterson claim to have proven this problem hard in the general case by using a reduction to partition. We tried to reproduce this in reading group, but found it very difficult. The issue is that one must build a gadget that forces a group of rectangular blocks to ``pack'' in a certain way - however there is great flexibility in the way you can move the blocks around. Joe claimed a possible proof at the end of the session, but it was not clear that he hadn't just constructed too complicated an example for the rest of us to understand...
More embarrassingly, we could not come up with an easy example of a set of blocks which could not be packed so at to realize the maximum sum of weights which can be stabbed by one point. This made us somewhat uncomfortable with out state of knowledge about the problem.
Steve believes that a heuristic similar to standard bin-packing heuristics (like first-fit decreasing) will give a constant factor approximation ratio. Only the proof is lacking to complete the result.