Challenge: Organizing a Lottery

Problem

---

Points and Segments Problem

Given a set of points and a set of segments on a line, compute for each point the number of segments it’s contained in.

Input: A list of $n$ segments and a list of $m$ points.

Output: The number of segments containing each point.

---

Suppose you are organizing an online lottery. To participate, a person bets on a single integer. You then draw several segments of consecutive integers at random. A participant’s payoff is proportional to the number of segments that contain the participant’s number. You need an efficient algorithm for computing the payoffs for all participants. A simple scan of the list of all ranges for each participant is too slow since your lottery is very popular: you have thousands of participants and thousands of ranges.

Input format: Two sequences of the starting points and ending points of $n$ segments and a list of $m$ points.

Output format: $m$ non-negative integers $k_{1}$ ...