Problem
Find maximum intervals overlap.
This problem is a classic algorithmic pattern, also known as below.
Meeting Rooms II - Given a list of intervals representing the start and end time of ‘N’ meetings, find the minimum number of rooms required to hold all the meetings.
OR
Interval Scheduling - Given list of jobs as intervals, find minimum number of machines required to run those jobs.
OR
Maximum Elephant Population - There is a number of elephants’ time spans given; here, a time span means the year of birth to the year of death. You have to calculate the period where the maximum number of elephants are alive.
OR
Peak Party Attendance - Consider a big party where a log register for guest’s entry and exit times is maintained. Find the time at which there are maximum guests in the party. Note that entries in the register are not in any order.
OR
Minimum Bus Platforms - At a bus station, you have a time-table for buses’ arrival and departure. You need to find the minimum number of platforms so that all the buses can be accommodated as per their schedule.
OR
Minimum Classrooms Required - Given an array of time intervals (start, end) for classroom lectures (possibly overlapping), find the minimum number of rooms required.
Examples
Example 1:
|
|
Example 2:
|
|
More Examples
Example 1 - Guest coming to party
|
|
Example 2 - Elephant with start and end date of there lives
|
|
Example 3 - Number of bus stations or bus station platform
|
|
Example 4 - Number of class rooms required
|
|
Solution
Method 1 - Use Count Array
Here is a straightforward approach:
- Inspect each time interval to determine the earliest and latest times (when the first and last guest respectively arrive and depart).
- Construct an array titled
count[]
with a length equal tomax – min + 1
. - Within every interval
[x, y]
, iterate fromi = x to y
and executecount[i – min]++
for each iteration. - Locate the count array’s largest value and note its index, known as ‘max_index’, then return the sum of
max_index + min
.
The memory requirement for the aforementioned method is O(max-min+1)
and its temporal complexity depends on interval lengths. In the extreme case where every interval stretches from ‘min’ to ‘max,’ the complexity is O((max-min+1)*n)
, with n
as the quantity of intervals.
Method 2 - Using Sorting of Intervals
Here is the pseudocode
- Split each date range into start date and end date.
- Sort the dates. If a start date and an end date are the same, put the end date first. For eg. in case of meeting rooms, we will have the meeting room free first, before someone can take it.
- Start with a count of 0.
- Iterate through the dates using a sweep-line algorithm:
- If you get a start date:
- Increment the count.
- If the current count is higher than the last best count, set the count, store this start date and set a flag.
- If you get an end date:
- If the flag is set, store the stored start date and this end date with the count as the best interval so far.
- Reset the flag.
- Decrement the count.
- If you get a start date:
Dry Run
Example: For input of elephant lives: 1990 - 2013 1995 - 2000 2010 - 2020 1992 - 1999
Split and sorted: (S = start, E = end) 1990 S, 1992 S, 1995 S, 1999 E, 2000 E, 2010 S, 2013 E, 2020 E
Iterating through them:
|
|
Example 2 -
|
|
Time complexity - O(nLogn)
time.
What if the number of elephants are very large?
For a (very) large number of elephants, it might be worth skipping the sort. You could create an array indexed by year with +1 for birth, -1 for death. O(e) to fill, and O(n) to sweep, where e is number of elephants and n is date range.
Following is the implementation of above approach. Note that the implementation doesn’t create a single sorted list of all events, rather it individually sorts arr[] and dep[] arrays, and then uses merge process of merge sort to process them together as a single sorted array.
Code
|
|
|
|
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n log n)
- 🧺 Space complexity:
O(1)
Method 3 - Using MinHeap on end times
We can also use minHeap to store the end intervals. We need to keep track of the ending time of all the meetings currently happening so that when we try to schedule a new meeting, we can see what meetings have already ended. We need to put this information in a data structure that can easily give us the smallest ending time. A Min Heap would fit our requirements best.
- Sort all the meetings on their start time.
- Create a min-heap to store all the active meetings. This min-heap will also be used to find the active meeting with the smallest end time.
- Iterate through all the meetings one by one to add them in the min-heap. Let’s say we are trying to schedule the meeting
m1
. - Since the min-heap contains all the active meetings, so before scheduling meeting
m1
we can remove all meetings from the heap that have ended beforem1
, i.e., remove all meetings from the heap that have an end time smaller than or equal to the start time ofm1
. - Now add
m1
to the heap. - The heap will always have all the overlapping meetings, so we will need rooms for all of them. Keep a counter to remember the maximum size of the heap at any time which will be the minimum number of rooms needed.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n log n)
- 🧺 Space complexity:
O(n)