educative.io

Educative

Point with maximum number of overlaps

Hi,

How do we proceed in knowing the point with maximum number of overlaps using the min heap technique of tracking the end times.

In the suggested solution, you keep track of the maximum concurrent meetings. When you reach a new maximum, you can store alongside it the point in time when this is happening (and update this for each time you reach a new maximum). This way you’ll get the point in time when you reached the maximum concurrent meetings.

@Guy_Rauscher Thanks for your reply. How do we calculate the point in time for the new maximum ? The minHeap will contains all overlapping meetings in it.

For instance if the minHeap currently contains - [ [3, 5], [4, 5], [2, 6] ] , then what should the point in time be for this state and how would it be computed ?

@Shruti_Ramesh, if you want just one point in time, how about taking the start of the last interval that you put in the heap (which is the point in which the heap reached it’s current size – meaning the point in which the current number of concurrent meetings is reached).
So you would save this point each time you reach a new maximum.