Average Cost Threshold Protocol with Minimum Thresholds: How to find the price?
There are two standard kinds of approaches to this sort of problem.


Check out segment trees and interval trees, and see if either of them are useful here (e.g., by augmenting the data structure).
Explore a sweep line algorithm.  In this sort of algorithm, we envision $p$ increasing from 0 upward as time progresses, and at each point in time, we keep track of the set of all intervals that contain $p$.  Thus, when $p$ hits the left endpoint of an interval, we add it to the set; when it reaches the right endpoint, we remove it from the set.  You can store the set as a balanced binary tree data structure, and then make it persistent using standard path copying techniques.  Now that you have this persistent data structure that captures all points in time, often you can find a way to solve your problem fairly rapidly.  Crucially, the tree will be of size $O(n \lg n)$ and depth $O(\lg n)$, so accesses are fast.


I haven't explored either of those approaches in the context of your particular problem, but these are two general techniques that are often useful for problems of this sort.