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

*Intervals of vacancies (working hours) may overlap

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

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. :(

CodePudding user response：

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.

CodePudding user response：

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.