Maximum Overlapping Intervals Problem
Consider an event where a log register is maintained containing the guest’s arrival and departure times. Given an array of arrival and departure times from entries in the log register, find the point when there were maximum guests present in the event.
Note that if an arrival and departure event coincides, the arrival time is preferred over the departure time.
For example,
arrival = { 1, 2, 4, 7, 8, 12 }
departure = { 2, 7, 8, 12, 10, 15 }
Output: Maximum number of guests is 3, present at time 7
Related Posts:
Find minimum platforms needed to avoid delay in the train arrival
1. Using Brute-Force (Quadratic Time Solution)
The idea is to find time t when the last guest leaves the event and create a count array of size t+2. Then fill the count array with the guest’s count using the array index to store time, i.e., for an interval [x, y], the count array is filled in a way that all values between the indices x and y are incremented by 1.
After the count array is filled with each event timings, find the maximum element’s index in the count array. This index would be the time when there were maximum guests present in the event.
The time complexity of this approach is quadratic and requires extra space for the count array. Following is the C++, Java, and Python program that demonstrates it:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; // Function to find the point when the maximum number of guests are present in an event void findMaxGuests(vector<int> const &arrival, vector<int> const &departure) { // Find the time when the last guest leaves the event int t = *max_element(departure.begin(), departure.end()); // create a count array initialized by 0 vector<int> count(t + 2); // fill the count array with guest's count using the array index to store time for (int i = 0; i < arrival.size(); i++) { for (int j = arrival[i]; j <= departure[i]; j++) { count[j]++; } } // keep track of the time when there are maximum guests int max_event_tm = 0; // find the index of the maximum element in the count array for (int i = 0; i <= t; i++) { if (count[max_event_tm] < count[i]) { max_event_tm = i; } } cout << "Event Time: " << max_event_tm << endl; cout << "The Maximum number of guests is " << count[max_event_tm] << endl; } int main() { vector<int> arrival = { 1, 2, 4, 7, 8, 12 }; vector<int> departure = { 2, 7, 8, 12, 10, 15 }; findMaxGuests(arrival, departure); return 0; } |
Output:
Event Time: 7
The maximum number of guests is 3
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
import java.util.Arrays; class Main { // Function to find the point when the maximum number of guests are // present in an event public static void findMaxGuests(int[] arrival, int[] departure) { // Find the time when the last guest leaves the event int t = Arrays.stream(departure).max().getAsInt(); // create a count array initialized by 0 int[] count = new int[t + 2]; // fill the count array with guest's count using the array index to store time for (int i = 0; i < arrival.length; i++) { for (int j = arrival[i]; j <= departure[i]; j++) { count[j]++; } } // keep track of the time when there are maximum guests int max_event_tm = 0; // find the index of the maximum element in the count array for (int i = 0; i <= t; i++) { if (count[max_event_tm] < count[i]) { max_event_tm = i; } } System.out.println("Event Time: " + max_event_tm); System.out.println("The maximum number of guests is " + count[max_event_tm]); } public static void main(String[] args) { int[] arrival = { 1, 2, 4, 7, 8, 12 }; int[] departure = { 2, 7, 8, 12, 10, 15 }; findMaxGuests(arrival, departure); } } |
Output:
Event Time: 7
The maximum number of guests is 3
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
# Function to find the point when the maximum number of guests are present in an event def findMaxGuests(arrival, departure): # Find the time when the last guest leaves the event t = max(departure) # create a count array initialized by 0 count = [0] * (t + 2) # fill the count array with guest's count using the array index to store time for i in range(len(arrival)): for j in range(arrival[i], departure[i] + 1): count[j] += 1 # keep track of the time when there are maximum guests max_event_tm = 0 # find the index of the maximum element in the count array for i in range(t + 1): if count[max_event_tm] < count[i]: max_event_tm = i print("Event Time:", max_event_tm) print("The maximum number of guests is", count[max_event_tm]) if __name__ == '__main__': arrival = [1, 2, 4, 7, 8, 12] departure = [2, 7, 8, 12, 10, 15] findMaxGuests(arrival, departure) |
Output:
Event Time: 7
The maximum number of guests is 3
2. Using Sorting (Linearithmic Time Solution)
The idea is to sort the arrival and departure times of guests and use the merge routine of the merge sort algorithm to process them together as a single sorted array of events. We maintain a counter to store the count number of guests present at the event at any point. While processing all events (arrival & departure) in sorted order,
- If the next event is arrival, increase the number of guests by one and update the maximum guest’s count found so far if the current guest’s count is more.
- If the next event is a departure, decrease the guest’s count by 1.
By following this process, we can keep track of the total number of guests at any time (guests that have arrived but not left). The time complexity of this approach is O(n.log(n)) and doesn’t require any extra space, where n is the total number of guests. Following is the C++, Java, and Python program that demonstrates it:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <iostream> #include <algorithm> #include <vector> using namespace std; // Function to find the point when the maximum number of guests are present in an event void findMaxGuests(vector<int> arrival, vector<int> departure) // no-ref, no-const { // sort the arrival and departure arrays in increasing order sort(arrival.begin(), arrival.end()); sort(departure.begin(), departure.end()); int checked_in = 0; // keep track of the total number of guests at any time int max_checked_in = 0; // keep track of the maximum number of guests in the event int max_event_tm = 0; // keep track of the time when there are maximum guests /* The following code is similar to the merge routine of the merge sort */ // Process all events (arrival & departure) in sorted order for (int i = 0, j = 0; i < arrival.size() && j < departure.size(); ) { // if the next event is arrival if (arrival[i] <= departure[j]) { // increment number of guests checked_in++; // update the maximum count of guests if needed if (max_checked_in < checked_in) { max_checked_in = checked_in; max_event_tm = arrival[i]; } // increment index of arrival array i++; } // if the next event is a departure else { // decrement number of guests checked_in--; // increment index of departure array j++; } } cout << "Event Time: " << max_event_tm << endl; cout << "The Maximum number of guests is " << max_checked_in << endl; } int main() { vector<int> arrival = { 1, 2, 4, 7, 8, 12 }; vector<int> departure = { 2, 7, 8, 12, 10, 15 }; findMaxGuests(arrival, departure); return 0; } |
Output:
Event Time: 7
The maximum number of guests is 3
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
import java.util.Arrays; class Main { // Function to find the point when the maximum number of guests are present // in an event public static void findMaxGuests(int[] arrival, int[] departure) { // sort the arrival and departure arrays in increasing order Arrays.sort(arrival); Arrays.sort(departure); int checked_in = 0; // keep track of the total number of guests at any time int max_checked_in = 0; // keep track of the max number of guests in the event int max_event_tm = 0; // keep track of the time when there are maximum guests /* The following code is similar to the merge routine of the merge sort */ // Process all events (arrival & departure) in sorted order for (int i = 0, j = 0; i < arrival.length && j < departure.length; ) { // if the next event is arrival if (arrival[i] <= departure[j]) { // increment number of guests checked_in++; // update the maximum count of guests if needed if (max_checked_in < checked_in) { max_checked_in = checked_in; max_event_tm = arrival[i]; } // increment index of arrival array i++; } // if the next event is a departure else { // decrement number of guests checked_in--; // increment index of departure array j++; } } System.out.println("Event Time: " + max_event_tm); System.out.println("The maximum number of guests is " + max_checked_in); } public static void main(String[] args) { int[] arrival = { 1, 2, 4, 7, 8, 12 }; int[] departure = { 2, 7, 8, 12, 10, 15 }; findMaxGuests(arrival, departure); } } |
Output:
Event Time: 7
The maximum number of guests is 3
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
# Function to find the point when the maximum number of guests are present in an event def findMaxGuests(arrival, departure): # sort the arrival and departure arrays in increasing order arrival.sort() departure.sort() checked_in = 0 # keep track of the total number of guests at any time max_checked_in = 0 # keep track of the maximum number of guests in the event max_event_tm = 0 # keep track of the time when there are maximum guests ''' The following code is similar to the merge routine of the merge sort ''' # Process all events (arrival & departure) in sorted order i = j = 0 while i < len(arrival) and j < len(departure): if arrival[i] <= departure[j]: # if the next event is arrival checked_in += 1 # increment number of guests # update the maximum count of guests if needed if max_checked_in < checked_in: max_checked_in = checked_in max_event_tm = arrival[i] i += 1 # increment index of arrival array # if the next event is a departure else: checked_in -= 1 # decrement number of guests j += 1 # increment index of departure array print("Event Time:", max_event_tm) print("The maximum number of guests is", max_checked_in) if __name__ == '__main__': arrival = [1, 2, 4, 7, 8, 12] departure = [2, 7, 8, 12, 10, 15] findMaxGuests(arrival, departure) |
Output:
Event Time: 7
The maximum number of guests is 3
3. Using Extra Space (Linear Time Solution)
We can improve solution #1 to run in linear time. The idea is to store only arrival and departure times in a count array instead of filling all values in an interval. This is done by increasing the value at the arrival time by one and decreasing the value after departure time by one.
After all guest logs are processed, perform a prefix sum computation to determine the exact guest count at each point, and get the index with maximum value. This index would be the time when there were maximum guests present in the event.
The time complexity of the above solution is O(n), but requires O(n) extra space. Following is the C++, Java, and Python program that demonstrates it:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; // Function to find the point when the maximum number of guests are present in an event void findMaxGuests(vector<int> const &arrival, vector<int> const &departure) { // Find the time when the last guest leaves the event int t = *max_element(departure.begin(), departure.end()); // create a count array initialized by 0 vector<int> count(t + 2); for (int i = 0; i < arrival.size(); i++) { count[arrival[i]]++; count[departure[i] + 1]--; } // keep track of the time when there are maximum guests int max_event_tm = count[0]; // perform a prefix sum computation to determine the guest count at each point for (int i = 1; i <= t; i++) { count[i] += count[i-1]; if (count[max_event_tm] < count[i]) { max_event_tm = i; } } cout << "Event Time: " << max_event_tm << endl; cout << "The Maximum number of guests is " << count[max_event_tm] << endl; } int main() { vector<int> arrival = { 1, 2, 4, 7, 8, 12 }; vector<int> departure = { 2, 7, 8, 12, 10, 15 }; findMaxGuests(arrival, departure); return 0; } |
Output:
Event Time: 7
The maximum number of guests is 3
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
import java.util.Arrays; class Main { // Function to find the point when the maximum number of guests are // present in an event public static void findMaxGuests(int[] arrival, int[] departure) { // Find the time when the last guest leaves the event int t = Arrays.stream(departure).max().getAsInt(); // create a count array initialized by 0 int[] count = new int[t + 2]; for (int i = 0; i < arrival.length; i++) { count[arrival[i]]++; count[departure[i] + 1]--; } // keep track of the time when there are maximum guests int max_event_tm = count[0]; // perform a prefix sum computation to determine the guest count at each point for (int i = 1; i <= t; i++) { count[i] += count[i-1]; if (count[max_event_tm] < count[i]) { max_event_tm = i; } } System.out.println("Event Time: " + max_event_tm); System.out.println("The maximum number of guests is " + count[max_event_tm]); } public static void main(String[] args) { int[] arrival = { 1, 2, 4, 7, 8, 12 }; int[] departure = { 2, 7, 8, 12, 10, 15 }; findMaxGuests(arrival, departure); } } |
Output:
Event Time: 7
The maximum number of guests is 3
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
# Function to find the point when the maximum number of guests are present in an event def findMaxGuests(arrival, departure): # Find the time when the last guest leaves the event t = max(departure) # create a count array initialized by 0 count = [0] * (t + 2) for i in range(len(arrival)): count[arrival[i]] += 1 count[departure[i] + 1] -= 1 # keep track of the time when there are maximum guests max_event_tm = count[0] # perform a prefix sum computation to determine the guest count at each point for i in range(1, t + 1): count[i] += count[i - 1] if count[max_event_tm] < count[i]: max_event_tm = i print("Event Time:", max_event_tm) print("The maximum number of guests is", count[max_event_tm]) if __name__ == '__main__': arrival = [1, 2, 4, 7, 8, 12] departure = [2, 7, 8, 12, 10, 15] findMaxGuests(arrival, departure) |
Output:
Event Time: 7
The maximum number of guests is 3
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)