0

I need to come up with an algorithm that can find free intervals on the timeline.

There is a time scale. From 00:00 to 24:00. Initially, when there are no vacancies, all the time is free, and the free interval is (0...1440) (in minutes).

For example, we add a vacancy, I mean that we set the working time for example from 08:00 to 21:00.

Now we will already have 2 free intervals. From 00:00 to 08:00. And from 21:00 to 24:00.

I'll attach pictures below to make it clear what I mean.

*Default variant example 1

*Intervals of vacancies (working hours) may overlap example 2

*Intervals of vacancies can be set without restrictions on the number, and intersect with anything, most importantly within 24 hours (1 day) example 3

The result that I expect: Initially, we have an array with 1 free interval from 0 to 1440 (in minutes), we call the function and pass working time to it, and at the output we get an updated array of intervals, in which there are already 2 intervals. Then we can add 1 more working time, and the output function will always give us the actual array with the correct number of intervals and the free time of the intervals themselves

For writing code I use swift, but I will understand the solution in Python or similar

I really hope for your help! I hope at least that the community will help put me on the right path, at the moment, I can't figure out which way to go. :(

Vladislav
  • 197
  • 7
  • What is the question here? – Phenomenal One Apr 07 '22 at 15:39
  • @PhenomenalOne Help with building the right algorithm – Vladislav Apr 07 '22 at 16:07
  • Union all the vacancy intervals, using an approach similar to [taking intersection over a continous range of values in python](https://stackoverflow.com/questions/71598681/taking-intersection-over-a-continous-range-of-values-in-python/71606431#71606431) or – Stef Apr 07 '22 at 16:12
  • or [Calculating the intersection between two angle intervals](https://stackoverflow.com/questions/37884021/calculating-the-intersection-between-two-angle-intervals) or [Combine two segments on the same circle if they overlap or intersect](https://stackoverflow.com/questions/40584625/combine-two-segments-on-the-same-circle-if-they-overlap-or-intersect/40585196#40585196) – Stef Apr 07 '22 at 16:12

2 Answers2

3

Turn intervals into pairs of start/end events, sort the events by time, then run through the list and keep a count of how many more start than end.

Any stretch of time where the two are equal becomes an interval in your answer.

Here is an explanatory example. Suppose we have the following intervals:

04:00 - 09:00
15:00 - 20:00
08:00 - 12:00

We get the following list of events from them.

04:00 start
09:00 end
15:00 start
20:00 end
08:00 start
12:00 end

Add 2 more to bookend the day

00:00 analysis_start
24:00 analysis_end

Which get sorted into:

00:00 analysis_start
04:00 start
08:00 start
09:00 end
12:00 end
15:00 start
20:00 end
24:00 analysis_end

And now we process them to come up with the following counts of open intervals:

00:00 - 04:00 0
04:00 - 08:00 1
08:00 - 09:00 2
09:00 - 12:00 1
12:00 - 15:00 0
15:00 - 20:00 1
20:00 - 24:00 0

And now the answer is where our tally was 0:

00:00 - 04:00
12:00 - 15:00
20:00 - 24:00
btilly
  • 43,296
  • 3
  • 59
  • 88
  • Your answer looks like a simple solution, but even with a piece of paper, I can't figure out what you mean? Could you explain a little more? – Vladislav Apr 11 '22 at 14:35
  • 1
    @Vladislav I added more explanation. – btilly Apr 11 '22 at 19:21
  • ok, I got to the point where we made new intervals. (00:00 - 04:00 0, 04:00 - 08:00 1.....) . As you pointed out, this is the number of "open intervals" but I did not understand what you mean. As far as I know, an open interval does not include endpoints, but having only these intervals, how can I determine this? (Unless, of course, I understood your idea correctly) – Vladislav Apr 12 '22 at 01:58
  • @Vladislav I meant open as in free. You said free intervals in your question. I did not mean the mathematical idea of an open interval. – btilly Apr 12 '22 at 16:32
  • now i figured it out. Your answer helped a lot, thanks – Vladislav Apr 12 '22 at 17:32
0

One possible way to do it could be to have an array of size 1440 (number of minutes). You can initialize all to 0 indicating all are free minutes.

For each vacancy interval you need to add, flip the values from 0 -> 1 in that interval, where 1 indicates working minute.

Whenever you need the array, you can iterate through the array and find "collections" of 0s and 1s for free-time and vacancies.

However, this is a very crude way of doing this and every query (update and select) takes linear time. You can do much better performancewise if you implement this whole thing as a segment tree (Read RMQ - range minimum query) where time complexity of your updates and selects will be logarithmic. Take this decision based on number of updates and selects and how you want your performance of code. eg. If total queries are ~10k, you need not go for segment tree. If they be ~10^5 or more, then you should.

vish4071
  • 5,135
  • 4
  • 35
  • 65