Find most optimal algorithm for given problem

Question

I'm trying to solve this problem from my textbook:

When a frisbee is thrown into a bucket, it gets stuck where the inner diameter of the bucket is smaller than the outer diameter of the frisbee. Analyse where in the bucket the frisbees gets stuck given the dimensions of the bucket and the radius of the frisbees. The bucket is always empty when a new frisbee is thrown, so they don't pile up in the bucket.

The bucket is symmetric along the y-axis. The picture shows what the cross section of the bucket can look like. The walls of the bucket are line segments that always connect at origo.

Input: (x_1,y_1),...,(x_m,y_m),r_1,...,r_n, all numbers are positive, m≤n and y_1 < y_2 < ...<y_m. (x_i,y_i) are the coordinates of the wall of the bucket, from the bottom to the top. r_i is the radius of the frisbee i.

Output: h_1,...h_n, where h_1 ≤ h_2 ≤...≤ h_n These are the different heights (y-coordinates) where the frisbees get stuck. The algorithm should be as efficient as possible.

Thanks in advance!

Answer 1

A lot of great algorithms have complexities that are dominated by an initial sort, so that really shouldn't set off any alarm bells for you.

Since the problem statement indicates that there are more frisbees than bucket segments, though, the complexity of O(n log n + m) that you achieve isn't quite optimal.

Note that a frisbee can only get stuck on the segment above a point that has a smaller x than all the points above it. Start by making a list of these points in y order, which you can do easily in O(m) time.

Because every point in the list has a smaller x than all the points after it, the list is monotonically increasing in x. For each frisbee, therefore, you can do a binary search in the list to find the last point with x < r. This takes O(log m) per frisbee for a total time of O(n log m + m), which is strictly smaller than O(n log n + m).

Answer 2

The worst case is when every frisbee lands on a different segment, and that's possible if m = n and if, for all j and i such that 0 < j < i, x_j < x_i. From there, the problem amounts to sorting the list of frisbees. So the complexity of the solution is indeed dominated by the sorting.

However, the complexity of sorting isn't necessarily O(n log n). If the maximum size of a frisbee has a limit l, and if l < n, then using radix sort will lower the complexity to O(n log l) (where log l is the number of digits of l or "key length").