Search code examples
algorithmintervals

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

Solution

  • 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