CODEWITHSUNDEEP
algorithmintervals
Vladislav
Vladislav

Reputation: 217

How to correctly find intervals between other intervals

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

Upvotes: 1

Views: 1204

Answers (2)

btilly
btilly

Reputation: 46507

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

Upvotes: 4

vish4071
vish4071

Reputation: 5287

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.

Upvotes: 0

Related Questions