algorithms – Maximize the minimum gap while scheduling within intervals?


There are N intervals in which a particular integer can be chosen. What is the maximum possible minimum gap between each integer if one integer is chosen for each of those intervals?

For example: Input: (2,4), (0,8), (3,15), (10,20)
We shall choose 2 in (2,4), 8 in (0,8), 14 in (3,15), 20 in (10,20)
Thus answer is 6. The distances between the integers need not be equal. We just need to maximize the minimum of those distance.

My effort

I’m supposed to use a greedy algorithm here (mentioned in the question) but I can’t get what do I do. I thought of sorting them according to the finishing time and then trying L = (maximum_range)/(N-1) as the first guess and starting from the first interval starting time I choose the next one at previous+L. If that is beyond the finishing time of the next one, I choose the finishing time and change the value of L to the new minimum (finishing_time – previous). If that is before starting time, I choose the starting time, else I choose the time previous+L itself. But this is not working in some cases like this: (2,4), (0,8), (3,9), (10,20) where it is choosing 2, 8, 9, 10 and giving the answer as 1. But the answer should be 4, where we choose 4, 0, 9, 13 respectively. I think my problem is with ordering them according to their finishing times, that fixes the element I start with, but in this case, the optimal solution does not start with (2,4) (least finishing time) itself, it should start with (0,8). Sorting according to starting time also does not do anything.