You are given as set of n time intervals {(s_1, _1), (s_2, _2), .., (s_n, _n}).
ID: 3855107 • Letter: Y
Question
You are given as set of n time intervals {(s_1, _1), (s_2, _2), .., (s_n, _n}). The interval (s) has a start time of s and an ending time of e You can think of each interval indicating that a "process" is active during that time. You may assume that e > s Or you can just think of them as horizontal line segments. You want to find the maximum overlap among all of the given time intervals. Your algorithm simple determines this maximum value and reports it. The diagram below illustrates an instance of the problem with 6 time intervals, each represented by horizontal line segments. For this instance, the algorithm would report 4 as the maximum overlap. Devise an algorithm solving this problem in O(n log n) time. Discussion/details: Time intervals are inclusive of their end points. As a result, if one interval ends at exactly the same time another begins, the two intervals are overlapping.Explanation / Answer
O(n logn) algorithm is as follows:
1. First make two arrays, one for storing starting times s1,s2...sn and one for storing exit times e1,e2...en .
2. sort the starting time array and ending time array in ascending order.
3. Now we will use algorithm similar to merge sort the two arrays. I will implement algorithm in C++
// process_run indicates number of process at a time, start is name of array containing starting times and exit array contains exiting times
int process_run= 1, max_process = 1;
int i = 1, j = 0;
// Similar to merge in merge sort to process
// both start and exit in sorted order
while (i < n && j < n)
{
// If next event in sorted order is arrival,
// increment count of process
if (start[i] <= exit[j])
{
process_run++;
// Update max_process if needed
if (process_run > max_process)
{
max_process = process_run; }
i++;
}
else // If event is exit, decrement count of process_run
{
process_run--;
j++;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.