Supose we have $n$ customers with interval that represent their range. For example, $[1,8], [2,5], [4,6], [1,9]$ for each customer. For a customer to have range coverage, a tower must be present within their range. For example, for customer $[1,8]$ to have coverage, a tower must be within range $[1,8]$. I need to make a greedy algorithm that will generate a list of tower locations that will cover all customers with the least number of towers. For the example above, the optimal solution will be location 4 or location 5 because only one tower at either location 4 or 5 will cover all customers. The algorithm should have a worst-case runtime of $O(n\log n)$.
I have tried the following method and failed. First, calcuate the length of each interval and make a tuple of (starting point, length) and add it to a array in assending order in respect to length. So, for the example above the list will look like $[(4,2), (2,3), (1,7), (1,8)]$. This will take $O(n)$ time to process. Second, I picked the customer with the smallest interval and tried to place a tower in the customer's interval. However, a problem rises, because greedy algorithms do not calcuate multiple options and then choose the optimal choice I have trouble of where to place the tower in the customer's interval. I have thought of three choices: at the very left, at the very right, at the middle. The middle, is statistically the most optimal one but not always correct because if the customer's interval is at the boundary and every other customer's interval starts at the very right point of the current customer's interval, the very right point is the right choice for this situation.
Any help for finding the optimal solution will be very helpful.
