Search code examples
arraysalgorithmobjectmaxindices

Two arrays one with time in, another with time out of something

Lets say we have 2 arrays, one of them (i.e. A) contains the time an object i will come into a room, and the other (i.e. B) contains the time i will leave. Neither of these are in any way sorted and their contents are Real numbers.

For example, object 3 has: A[3]=0.785 and B[3]=4.829.

How would you in O(nlogn) find the max objects in the room at any given time t?

Solution

  • You can try this:

    • initialize number of objects as zero
    • sort both arrays
    • while there are elements left in either array
      • determine which array's first value is smaller
      • if the first value in "enter" is smaller, increment number of objects and pop that value
      • if the first value in "leave" is smaller, decrement number of objects and pop that value
      • check whether you found a new maximum number of objects

    If you can not "pop" elements from the arrays, you can use two index variables instead; also, you will have to add cases for when one of the arrays is already empty.

    Sorting has O(nlogn), and the following loop has O(2*n), thus O(nlogn) in total.