I would like a help in the following question of finding an algorithm to the following problem:

Given a pair list (a₁,b₁),...,(a_n,b_n) , where a_i is the entry date of a person i to the city and b_i is the departure date of person i. Assume that you enter the city at the beginning of the day, and leave the city at the end of the day.

For example, if a person entered the city on the 4th of the month, and left on the 12th of the same month, then he was in the city 9 days. Propose an algorithm as efficient as possible for the calculation of the maximum number of people who were in the city at the same time

My try: Use two arrays, one for the entry and one array for the departure. Sort the arrays in ascending order. Iterate through the sorted arrays and for each iteration, if the current element in the entry array is smaller (or equal) to the current element in the departure array then increment a counter, otherwise we decrement the counter. After each iteration, update another variable for the maximum counts to be the maximum between the counter variable and the maximum counts variable. Then print the maximum counts.

This is done in O(n log n). Is there a more efficient way to solve this problem?

CodePudding user response：

1. Create an array(lets say count) of size 33 and initialize it all with 0s.

2. Now traverse through the pair list and for every pair (ai, bi), do count[ai] and count[bi 1]--

3. Now take a variable called numberOfPeople and perform following loop

   int numberOfPeople = 0, maxNumberOfPeople = 0;`
   
   for(int i=1;i<=31;  i){
        numberOfPeople  = count[i];
        maxNumberOfPeople = max(numberOfPeople, maxNumberOfPeople);
    }
   

Inside the loop, for every i, numberOfPeople will represent the number of people present in the city on ith day. The time complexity of this solution is O(n)

This assumes that there are only max 31 days in a month and we are taking about a single month only. The solution can easily be modified if that is not the case

CodePudding user response：

Split each pair in two events: arrival and departure and put them into a collection.

List<(DateTime time, bool isArrival)> events = ...

Then sort the collection by time, e.g.

events.Sort((left, right) => left.time.CompareTo(right.time)); 

Finally, scan the collection: on arrival add 1, on departure subtract 1 while computing maximum:

int result = 0;
int current = 0;

foreach (var event in events) 
  if (event.isArrival) { 
    count  = 1;

    result = Math.Max(result, count);
  }
  else
    count -= 1;

It is sorting procedure that defines time complexity here. In general case we have typical O(n * log(n)) time complexity; however, if we have real dates, which are restrited (say, the all can be represented in yyyy-MM-dd format) we can perform radix sort and get O(n) time complexity.