Office hours will take place between time T = 0 to T = 60mins and all students c

Question

Office hours will take place between time T = 0 to T = 60mins and all students can potentially attend. Each student Si writes to the professor in advance by specifying a time interval (`i , ui) when he/she will attend office hours. Note that 0 `i < ui 60. Given the time intervals for the n students I1, . . . , In, find the maximum number of students who will be at the office hours at any point in time. Your algorithm should run in time (n log2 (n)). Example: Inputs n = 5 students and intevals are

I1 : (0, 15), I2 : (15, 20), I3 : (0, 22), I4 : (19, 20), I5 : (21, 40)

The maximum number of students at any time instant is 3. If a student i arrives at time t, and another student j leaves at the same time t, then we assume that the leaving happens before the arrival.

Explanation / Answer

We can solve the above problem in O(nLogn) time. The idea is to consider all evens in sorted order. Once we have all events in sorted order, we can trace the number of trains at any time keeping track of trains that have arrived, but not departed.

For example consider the above example.

    arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00}
    dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00}

All events sorted by time.
Total students at any time can be obtained by subtracting total
departures from total arrivals by that time.
Time     Event Type     Total students at this Time                             
9:00       Arrival                  1
9:10       Departure                0
9:40       Arrival                  1
9:50       Arrival                  2
11:00      Arrival                  3
11:20      Departure                2
11:30      Departure                1
12:00      Departure                0
15:00      Arrival                  1
18:00      Arrival                  2
19:00      Departure                1
20:00      Departure                0

Maximum students = 3

// Program to find maximum number of students at any time
#include<iostream>
#include<algorithm>
using namespace std;

// Returns minimum number of students at a time
int findStudentNumber(int arr[], int dep[], int n)
{
   // Sort arrival and departure arrays
   sort(arr, arr+n);
   sort(dep, dep+n);

   // student_no indicates number of students at a time
   int student_no = 1, result = 1;
   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
      // students
      if (arr[i] < dep[j])
      {
          student_no++;
          i++;
          if (student_no > result) // Update result if needed
              result = student_no;
      }
      else // Else decrement count of students
      {
          student_no--;
          j++;
      }
   }

   return result;
}

// Driver program to test methods of graph class
int main()
{
    int arr[] = {900, 940, 950, 1100, 1500, 1800};
    int dep[] = {910, 1200, 1120, 1130, 1900, 2000};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Maximum number of students = "
         << findStudentNumber(arr, dep, n);
    return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

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