Given a set of intervals, how do we find the maximum number of intervals overlapping at any point of time.
For example let us consider the following intervals.
{ (0,2), (3, 7), (4,6), (7,8), (1,5) }
The maximum number of intervals overlapped is 3 during (4,5).
This can be asked in many forms in a programming competition. This CodeChef problem is one such an example. Go and test your knowledge if you have some idea about how to solve this.
Let us look at the solution approaches.
We first consider all the start and end point as a single entity and sort them in ascending order according the following criteria.
- If the times are different, just sort according to time.
- If the times are equal, we first place the end of interval.
Then we take a counter and a maximum counter.
Iterate through all the points
- If the point is start of interval we increment the counter.
- Keep track of maximum counter
- Otherwise we decrement the counter
At the end of this, we have the required result in maximum counter.
Another alternative solution could be to use the merge procedure used in merge sort. The steps are similar to the merge procedure.
- Sort all the starting points and ending points in ascending order
- Try to merge them into a single list
- Use two variables overlap, and max_overlap to keep track of the current overlap and maximum overlap we have seen so far.
- As long as we take element from starting point of the interval, increment overlap and update max_overlap.
- If we are taking en element from ending point of the interval, decrement overlap.
At the end of this procedure, we have the answer in max_overlap.
Below is the simple C++ implementation of the above algorithms.