Find the point where maximum intervals overlap - GeeksforGeeks

Find the point where maximum intervals overlap - GeeksforGeeks
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 register are not in any order.

void findMaxGuests(int arrl[], int exit[], int n)

{

   // Sort arrival and exit arrays

   sort(arrl, arrl+n);

   sort(exit, exit+n);

   // guests_in indicates number of guests at a time

   int guests_in = 1, max_guests = 1, time = arrl[0];

   int i = 1, j = 0;

   // Similar to merge in merge sort to process

   // all events in sorted order

   while (i < n && j < n)

   {

      // If next event in sorted order is arrival,

      // increment count of guests

      if (arrl[i] <= exit[j])

      {

          guests_in++;

          // Update max_guests if needed

          if (guests_in > max_guests)

          {

              max_guests = guests_in;

              time = arrl[i];

          }

          i++;  //increment index of arrival array

      }

      else // If event is exit, decrement count

      {    // of guests.

          guests_in--;

          j++;

      }

   }

   cout << "Maximum Number of Guests = " << max_guests

        << " at time " << time;

}

Below is a Simple Method to solve this problem.

1) Traverse all intervals and find min and max time (time at which first guest arrives and time at which last guest leaves)

2) Create a count array of size ‘max – min + 1′. Let the array be count[].

3) For each interval [x, y], run a loop for i = x to y and do following in loop.
     count[i – min]++;

4) Find the index of maximum element in count array. Let this index be ‘max_index’, return max_index + min.

Above solution requires O(max-min+1) extra space. Also time complexity of above solution depends on lengths of intervals. In worst case, if all intervals are from ‘min’ to ‘max’, then time complexity becomes O((max-min+1)*n) where n is number of intervals.

Different solution:
http://siyang2notleetcode.blogspot.com/2015/02/maximum-overlapping-interval.html
Read full article from Find the point where maximum intervals overlap - GeeksforGeeks