How to determine the occurrence in a period of time?

W

wangler2016-02-12 17:08:42

Algorithms

wangler, 2016-02-12 17:08:42

Hello.
I ask for help to add an algorithm for solving such a problem by calculating the time:
There are two timestamp lines in the plate (the beginning of the interval and the end). For example from 13-30 to 14-30.
There are several such records, at the same time interval. How can you determine which gaps are already "occupied"? Perhaps there is already a solution in the form of a ready-made library for working with such values, in any case I will be glad for any advice.

Reply

Answer the question

In order to leave comments, you need to log in

2 answer(s)

D

delfphe, 2016-02-16
@delfphe

I'm not sure about the efficiency of these algorithms, but for some reason a segment tree and a sweeping straight line come to mind.
You can, for example, break all the time into segments of, say, five minutes. Then, for example, room[0] == 1 means that the room is occupied from 00:00 to 00:05. In this case, queries for the sum in the segment tree can check the availability of a room in a given period of time (the sum is zero), and by adding a value to all elements in the segment, you can "book" the room. The complexity of both queries is O(log n), where n is the size of the room[] array.
e-maxx.ru/algo/segment_tree
codeforces.com/blog/entry/18051
There is an approach that is simpler and, under certain conditions, even more efficient: a one-dimensional sweeping straight line. We will operate with events like (13-30, open), (14-30, close). Let's go through the sorted events, keeping the number of intervals open at the moment. If between the beginning of the request and the end of the request the counter was not equal to zero, the interval is busy. Complexity (in case of an array with events) - O(m logm) build, O(m) query, O(m) add interval, where m is the number of events.

V

Vladimir Olohtonov, 2016-02-12
@sgjurano

It is necessary to find the complete coverage of the given intervals using the minimum number of combined intervals.
Did I understand your task correctly? A similar algorithm was considered in the course on algorithms on stepic.org, but it was not possible to find its name from the phone.