There are n points on the x-axis, each with an integer coordinate in the range [0, n^3 ]. We can cover these points with k segments, each of length L (a segment can cover all the points within it, including the endpoints). Given k and n, how to find the minimum L in O(nlogn) time?

I've thought that if n<=k, then L ->0, but when n>k, things start to be complicated, hope you could help me out.

CodePudding user response：

First, do a binary search on L. Assume there's a magic function check(L) that returns whether we can cover the points with segments of length L, we use binary search to find the minumum L such that check(L) returns true.

Then, let's implement that magic function. We can place our segments greedily: find the leftmost not covered point, and place a segment so its left endpoint is at that point. Repeat this k times, and check if all n points have been covered.

Binary search calls check(L) O(log n) times, each call to check(L) takes O(n) if we have an order list of points (just scan the array from left to right), in total this is O(n log n). Since the list of points don't change, we can pre-sort the list, which also takes O(n log n) time. So the time complexity of this algorithm is O(n log n).