PROBLEM 2: algorithm design (50 points): You are given as set of n time interval

Question

PROBLEM 2: algorithm design (50 points): You are given as set of n time intervals (se)se. SThe interval (s,e) 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 eps,. 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 simply 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. end start overlap: overlap: overlap: overlap: | overlap: time Devise an algorithm solving this problem in O(n logn) time Discussion/details: . Time intervals are inclusive of their end points. As a result, . The interval start and end times are given as floating point . The intervals are given in an arbitrary order if one interval ends at exactly the same time another begins, the two intervals are overlapping. numbers.

Explanation / Answer

I am answering 3rd question :

int missing_integer(int arr[], int len)
{
   int first,last,mid;
    if(len <= 0)
        return -1;

    first = 0;
    last = len - 1;
    while(first <= last)
    {
        mid= (first + last) /2 ;
        if(arr[mid] != mid)
        {
            if(mid == 0 || arr[mid - 1] == mid - 1)
                return mid;
              
            last = mid - 1;
        }
        else
            first = mid + 1;
    }

    if(first == len )
        return len;

    return -1;
}

Description of solution :
------------------------

As given array is sorted array of N distinict integers
It means array values are equal to their indexes.
i.e Let say a distinct sorted array of size 4 , which has elements from 0 to n-1
indexes        : 0 1 2 3
array_elements : 0 1 2 3

the above case is if no number is missing

Now let us say If a number is missing as X
The numbers which are less than X are place under right position
but numbers after X are located in wrong positions by one index
i.e X+1 element is placed at index X
So we need to perform a search operation on given array to find out the index of missing integer

For this we can use Binary search as given array is sorted which has time complexity of 0(lgn)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.