What algorithm should be used to find the maximum intersection of a set of segments?

I

isxaker2014-10-01 16:35:28

Algorithms

isxaker, 2014-10-01 16:35:28

There is a task:
The museum registers during the day the time of arrival and departure of each visitor. Thus, N pairs of values were obtained per day, where the first value in the pair shows the visitor's arrival time and the second value - the time of his departure. Find the period of time during which the maximum number of visitors were in the museum at the same time.
Is there a well-known algorithm for solving such problems?
Is the segment tree for the sum suitable for solving this problem?

Reply

Answer the question

In order to leave comments, you need to log in

3 answer(s)

D

Dmitry Entelis, 2014-10-01
@DmitriyEntelis

@isxaker You yourself suggested a good option in my opinion
stackoverflow.com/questions/2244964/finding-number...
What is the question? :)

M

meat, 2014-10-08
@meat

since precision is not required, create an array of 24 * 60 integers, and fill it with each segment, adding one to each element. then go through the resulting array, and find the maximum. O(n)

3

386DX, 2014-10-01
@386DX

If you do not need perfect accuracy, then you can take a day as 5 * 228 minutes (24 hours - x-axis) and check every five minutes how many visitor segments are included in these 5 minutes. Then from results to search for a maximum.