Maximum Intervals Overlap Count
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:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Explanation: We need two meeting rooms
room1: (0,30)
room2: (5,10),(15,20)
Example 2:
Input: intervals = [(2,7)]
Output: 1
Explanation:
Only need one meeting room
More Examples
Example 1 - Guest coming to party
Input: intervals =[[1,4], [2,5], [9,12], [5,9], [5,12]]
Output: 3
Explanation: First guest in array arrives at 1 and leaves at 4,
second guest arrives at 2 and leaves at 5, and so on.
There are maximum 3 guests at time 5.
Example 2 - Elephant with start and end date of there lives
Input: intervals =[[1990,2013], [1995,2000], [2010,2020], [1992,1999]]
Output: 3
Explanation: There are 3 elephants living in period [1995, 1999].
Example 3 - Number of bus stations or bus station platform
Bus Arrival Departure
BusA 0900 hrs 0930 hrs
BusB 0915 hrs 1300 hrs
BusC 1030 hrs 1100 hrs
BusD 1045 hrs 1145 hrs
Output: 3
Example 4 - Number of class rooms required
class room lectures timings = [(30, 75), (0, 50), (60, 150)]
Output: 2
Solution
Video explanation
Here is the video explaining this method in detail. Please check it out:
<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/odBaY0mnqlw" frameborder="0" allowfullscreen></iframe></div>
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 yand 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:
count = 0
lastStart = N/A
1990: count = 1
count = 1 > 0, so set flag
and lastStart = 1990
1992: count = 2
count = 2 > 0, so set flag
and lastStart = 1992
1995: count = 3
count = 3 > 0, so set flag
and lastStart = 1995
1999: flag is set, so
record [lastStart (= 1995), 1999] with a count of 3
reset flag
count = 2
2000: flag is not set
reset flag
count = 1
2010: count = 2
since count = 2 < 3, don't set flag
2013: flag is not set
reset flag
count = 1
2020: flag is not set
reset flag
count = 0
Example 2 -
arr[] = {1, 2, 10, 5, 5}
dep[] = {4, 5, 12, 9, 12}
Below are all events sorted by time. Note that in sorting, if two
events have same time, then arrival is preferred over exit.
Time Event Type Total Number of Guests Present
------------------------------------------------------------
1 Arrival 1
2 Arrival 2
4 Exit 1
5 Arrival 2
5 Arrival 3 // Max Guests
5 Exit 2
9 Exit 1
10 Arrival 2
12 Exit 1
12 Exit 0
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 - Interval Class
Java
Using Interval Class
We can define our interval class:
class Interval {
public int start;
public int end;
public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
public int minMeetingRooms(int[][] intervals) {
int n = intervals.length;
List<Interval> intervalList = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
intervalList.add(new Interval(intervals[i][0], intervals[i][1]));
}
return maxOverlapIntervalCount(intervalList);
}
private int maxOverlapIntervalCount(List<Interval> intervals) {
// break and sort the intervals
List<Integer> start = intervals.stream().map(i -> i.start).sort();
List<Integer> end = intervals.stream().map(i -> i.end).sort();
int maxOverlap = 0;
int currentOverlap = 0;
int i = 0;
int j = 0;
while (i < intervals.size()) {
if (start[i]<end[j]) {
currentOverlap++;
maxOverlap = Math.max(maxOverlap, currentOverlap);
i++;
} else {
currentOverlap--;
j++;
}
}
return maxOverlap;
}
Code - Another variant of Interval class
Java
static class IntervalPoint implements Comparable {
int timestamp;
boolean isStart;
public IntervalPoint(int timestamp, boolean isStart) {
this.timestamp = timestamp;
this.isStart = isStart;
}
@Override
public int compareTo(Object o) {
if (o instanceof Endpoint) {
IntervalPoint other = (Endpoint) o;
int result = Integer.compare(timestamp, other.timestamp);
//in case a result is 0, then one which starts early should be returned
if (result == 0) {
return Boolean.compare(((Endpoint) o).isStart, isStart);
} else {
return result;
}
}
return 0;
}
}
Now, the solution code:
public int minMeetingRooms(int[][] intervals) {
int n = intervals.length;
List<IntervalPoint> intervalList = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
intervalList.add(new IntervalPoint(intervals[i][0], true));
intervalList.add(new IntervalPoint(intervals[i][1], false));
}
return maxOverlapIntervalCount(intervalList);
}
public int maximalOverlapped(List<IntervalPoint> intervalPoints) {
Collections.sort(intervalPoints);
int maxOverlap = 0;
int cur = 0;
for (IntervalPoint intervalPoint: intervalPoints) {
if (intervalPoint.isStart) {
++cur;
maxOverlap = Math.max(maxOverlap, cur);
} else {
--cur;
}
}
return maxOverlap;
}
Code
This is using intervals array.
Java
class Solution {
public int minMeetingRooms(int[][] intervals) {
int n = intervals.length;
// Separate start and end times
int[] startTimes = new int[n];
int[] endTimes = new int[n];
for (int i = 0; i < n; i++) {
startTimes[i] = intervals[i][0];
endTimes[i] = intervals[i][1];
}
// Sort both arrays
Arrays.sort(startTimes);
Arrays.sort(endTimes);
int sPtr = 0;
int ePtr = 0;
int currentRooms = 0;
int maxRooms = 0;
while (sPtr < n) {
// If a meeting starts before an existing one ends
if (startTimes[sPtr] < endTimes[ePtr]) {
currentRooms++;
sPtr++;
} else { // An existing meeting ends
currentRooms--;
ePtr++;
}
maxRooms = Math.max(maxRooms, currentRooms);
}
return maxRooms;
}
}
Python
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
n = len(intervals)
# Separate start and end times
start_times = [interval[0] for interval in intervals]
end_times = [interval[1] for interval in intervals]
# Sort both arrays
start_times.sort()
end_times.sort()
s_ptr = 0
e_ptr = 0
current_rooms = 0
max_rooms = 0
while s_ptr < n:
# If a meeting starts before an existing one ends
if start_times[s_ptr] < end_times[e_ptr]:
current_rooms += 1
s_ptr += 1
else: # An existing meeting ends
current_rooms -= 1
e_ptr += 1
max_rooms = max(max_rooms, current_rooms)
return max_rooms
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
m1we 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
m1to 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
Using int[] array as interval
Java
class Solution {
public int minMeetingRooms(int[][] intervals) {
// Sort the intervals by their start times
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
// Use a min-heap to store the end times of meetings
// The heap will always give us the meeting that finishes earliest
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// Add the end time of the first meeting to the heap
minHeap.add(intervals[0][1]);
// Iterate through the rest of the meetings
for (int i = 1; i < intervals.length; i++) {
// If the current meeting's start time is greater than or equal to
// the earliest end time in the heap, it means a room is free.
// We can reuse that room.
if (intervals[i][0] >= minHeap.peek()) {
minHeap.poll(); // Remove the old meeting's end time
}
// Add the current meeting's end time to the heap
minHeap.add(intervals[i][1]);
}
// The size of the heap at the end represents the minimum number of rooms required
return minHeap.size();
}
}
Python
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
# Sort the intervals by their start times
intervals.sort(key=lambda x: x[0])
# Use a min-heap to store the end times of meetings
# The heap will always give us the meeting that finishes earliest
min_heap = []
# Add the end time of the first meeting to the heap
heapq.heappush(min_heap, intervals[0][1])
# Iterate through the rest of the meetings
for i in range(1, len(intervals)):
# If the current meeting's start time is greater than or equal to
# the earliest end time in the heap, it means a room is free.
# We can reuse that room.
if intervals[i][0] >= min_heap[0]: # min_heap[0] gives the smallest element
heapq.heappop(min_heap) # Remove the old meeting's end time
# Add the current meeting's end time to the heap
heapq.heappush(min_heap, intervals[i][1])
# The size of the heap at the end represents the minimum number of rooms required
return len(min_heap)
Code - Using Interval Class
Java
public static int minMeetingRooms(List<Interval> intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a.start, b.start)); // sort intervals by start time
PriorityQueue<Interval> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.end, b.end)); // minHeap by end
int max = 0;
for (Interval interval : intervals) {
while (!minHeap.isEmpty() && minHeap.peek().end <= i.start) {
minHeap.poll();
}
minHeap.offer(interval);
max = Math.max(max, minHeap.size());
}
return max;
}
Complexity
- ⏰ Time complexity:
O(n log n) - 🧺 Space complexity:
O(n)