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.

  • $\begingroup$ Can you solve this problem in case when all intervals are disjoint? $\endgroup$ – Vladislav Bezhentsev Oct 16 '20 at 0:24
  • $\begingroup$ The stated problem is not easier than "Given a set of intervals and an integer $L$, find point assignments to intervals such that a distance between any 2 points is at least $L$". And this is some reduced form of an integer programming feasibility problem. Though I am not sure, but it still seems to be an NP-hard problem. $\endgroup$ – Vladislav Bezhentsev Oct 16 '20 at 1:28
  • $\begingroup$ @VladislavBezhentsev The original problem was given with respect to time slots but it required the time between two visits can be any real number (not necessarily integers) but the answer asked to round of the final answer to nearest seconds. Does this make any difference with using integer vs using real numbers. $\endgroup$ – Shubhraneel Pal Oct 16 '20 at 3:57
  • 1
    $\begingroup$ Duplicate of cs.stackexchange.com/questions/35341/… I believe $\endgroup$ – Throckmorton Oct 16 '20 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.