CareerCup

I can think of an nlog(n) solution. Thought is: for each guest, say his time span is [a, b], we reorgnize this data to: [a, in] and [b, out], which means at time a, a guest came in, and at time b, a guest left. Do this for all guests, we have a bunch of data like [x, in] and [y, out]. Sort all these data by the time part in ascending order. Then traverse from the earliest time, if the data is [in], have a counter++; if it is [out], have the counter--. After all, the max of counter is the answer.

I wrote this naive solution. Comments are welcome.

1) Have an integer array of size 24 initialize to 0. lets call it t.
2) for each pair of start and end times, increment the t array corresponding indices from start to end
3) Finally check for the maximum in the t array and return corresponding index.

int getmax(const vector<pair<int,int> >& vp){
  vector<int> t(24,0);
  pair<int, int> p;
  for(unsigned int i=0;i<vp.size();i++){
    p = vp[i];
    for(int j = p.first;j<=p.second;j++){
      t[j]++;
    }
  }
  int currmax = -1;
  for(int i=0;i<24;i++){
    if(t[i] > currmax){
      currmax = i;
    }
  }
  return currmax;
}

it was not 1-24 range of numbers. tht would be so easy.say the time limit is 10000..
there is some DP approach of O(n) tht dont require extra space but i was not able to recall tht at that time :(
i am looking for that one

On top of my mind, It seems problem of identifying max-clique in graph?

consider each person as node in graph, draw edge if two person overlaps in time inclusive of arrival and departure - O(n^2)
find max-clique, O(??) nodes in max clique will be present at party.

Regarding above solution if max(depart time) > 2^n, it will O(2^n) solution.

OP are we looking at only start-end times?


For sample:
[1,4] [2,6] [9,12] [5,9] [5,12]
is answer still same? t=5

This problem is similar to problem BYTESE2 on spoj.Here is the Acc. O(NlogN) solution:

#include<iostream>
using namespace std ;
#define MAXN 105
int n,a[MAXN],b[MAXN] ;
main()
{
 int i,j,runs ;
 scanf("%d",&runs) ;
 while(runs--)
 {
  scanf("%d",&n) ;
  for(i=0;i<n;i++) scanf("%d%d",&a[i],&b[i]) ;
  sort(a,a+n) ;
  sort(b,b+n) ;
  int cur = 0,p1 = 0,p2 = 0,ret = 0 ;
  while(p1 < n && p2 < n)
  {
   if(a[p1] <= b[p2]) cur ++,p1 ++ ;
   else cur --,p2 ++ ;        
   ret >?= cur ;
  }
  printf("%d\n",ret) ;
 }
}

Note that it doesn't require extra space(arrays 'a' and 'b'are for storing intervel end points)...

we can have a hashtable and enter the time as a key and value as num of persons. For each entry and exit time modify the value for each same time. return the key having maximum num of people as value.

Does ret return the number of maximum guests or the time? Can you explain the logic of comparison after sorting both arrays?

@cool indeed i have seen the same problem on z-training too thats why i am saying that there is some DP solution exist for this problem.well anyways nlogn solution seems gud enof and i actually gave that solution in the interview.lets see if the google guy knows the O(n) solution ^^

j

I guess the problem would be more interesting if the interval of time where most people were present in the party was asked...
Though the solution would be not very involved, it'd using Interval trees; mapping each interval in the tree and increasing counts on the intervals already visited. At the end, traverse the entire tree to find the max count interval node.
This data structure could be tweaked to find solution to stated problem as well..

I first think of a naive approach.

Let's say there are m time slots and n guests. The input will be a list of entry in form of [x, y], where 0 <= x <= y <= m. The input is not sorted in any favor.

We create an array of size m. Initialize each element to be value 0. Then scan the input; for each input [x, y], perform the following:

for i in [x...m) array[x]++
    for j in [y...m) array[y]--

Finally, output the index of the largest element in the array.

The code works below (Java):

// Assume we have the following data type
public class Entry {
     public int enterTime;
     public exitTime;
}

public int maxGuest(Entry[] entries, int m) {
     int[] table = new int[m];
     for (Entry e : entries) {
          for (int i = e.enterTime; i < m; i++) table[i]++;
          for (int i = e.exitTime; i < m; i++) table[i]--;
     }
     int max = 0;
     for (int i = 1; i < m; i++) {
          if (table[i] > table[max]) max = i;
     }
     return max;
}

O(n^2) time, O(m) space.

Are the IN times sequential?

what's the best? O(N)? or O(nlgn)?

One approach using DP:

Maintain two arrays Entry and Exit.
Scan the input and populate these two arrays.

for example:
For input [1,4],[2,7],[3,5]
the values will be Entry: 1,1,1,0,0,0,0
Exit: 0,0,0,1,1,0,1

Num(i) - Number of guests present at time i;

Num(i) = Num(i-1) + Entry(i) - Exit(i-1);

i with Maximum (Num(i) will be the final answer.

Time: O(n) and space O(3n)(~ O(n))

There is the same approach as some of the previous comments, but hopefully more clear.

Assume we have m intervals (e.g. m=57). First, go through all the intervals and check that the arrive time is smaller or equal to the leave time (always check your input).

Create an array of length 2*m (114), and put in the array both the arriving and the leaving times. Keep a bit for each time to know if this is an arriving time, or a leaving time. Sort the array by the time. In case of a tie, ALWAYS put all the arriving times before all the leaving times (only if there is a tie).

This takes O(m*log(m)), but if you know that the times are integers , or that they are in a certain interval, you can do it in O(m) using radix sort, count sort, etc.

Go through this array of length 2*m. For each element which is marked as an ival, add 1 to a counter. For each person that leaves, subtract one. The maximal value of the counter gives you the maximal number of people at the party.

You can also keep a separate stack. When a person comes to the party, you push one element in the stack; when someone leaves, you pop it. The maximum height of the stack is your answer. (This also assumes the existence of the sorted array of length 2*m).

Why cant we just use an array of integers and just increment each integer by one for the interval that a person is present at the party? Then just return the largest interval?

I meant return largest integer, not interval.

I meant return largest integer, not interval.

check wikipedia for Marzullo's algorithm. It solves the exact same problem.

I have a O(n) solution. First we must see that for each interval [a,b], based on specification, the guest doesn't leave at time b, i.e. we count the that guest at time b, we make a modification that the guest leaves at b+1, therefore, the interval becomes [a,b+1].

Next, sort the intervals all together. For example, [1,4], [2,5], [9,12], [5,9], [5,12] becomes 1 2 5 5 5 6 9 10 13 13 (remember we add one to each leaving time). Then we iterate this series, for each number we encounter, if it is entry time, the guest number +1, if it is the leaving time, the guest time -1. We maintain the maximal number along the process. In this example, it is easy to see that the maximal guest number is 3 and it happens at two time spot 5, and, 9.

"For example, [1,4], [2,5], [9,12], [5,9], [5,12] becomes 1 2 5 5 5 6 9 10 13 13 (remember we add one to each leaving time)." huh??

Here is another one.

1. sort the intervals non decreasingly on start time.
2. maintain a min heap of end times as we scan the sorted intervals sequentially. insert the end time of an interval t(start, end) into the min queue q as follows

while (start > q.min())
    q.pop();
q.insert(end);

3. we keep a max size of the min queue during insertion, also the time t for the max size. return t after we are done insertion.

Runtime is O(nlogn). Sorting is O(nlogn), min queue removal and insertion takes O(logn) each. Total scan of intervals also takes O(nlogn). Space is O(n) if all intervals overlap.

Here is the logic for the algorithm. A set of intervals overlap if all the intervals start before the earliest end time of these intervals. The min queue maintains the end time of the current overlapping intervals. Since intervals are sorted on the start time, when we process the next interval t(start, end), if

(a) t starts before any overlapped interval ends, i.e, end < q.min(), then t overlaps with these intervals.

(b) t starts after some overlapped intervals end which means t doesn't overlap with these intervals. In this case, we keep remove q.min() until start <= q.min(), i.e., t overlaps with the intervals whose end time is still in q.

Since the example in the question seems to suggest that we should consider entry time before exit time, I just got an idea from reading Julian's answer that proposes incrementing the exit time. Let's first multiply all the entry/exit time by 2. Furthermore, add 1 to each exit time. So [1, 4] [2, 5] [9, 12] [5, 9] [5, 12] becomes [2, 9] [4, 11] [18, 25] [10, 19] [10, 25].

This has 2 benefits. First we respect the implicit rule that entry should be accounted for before exits. Secondly, we can now use even/odd to indicate whether it's an entry/exit event. So at t=10 we have the max guests, and we simply divide that by 2 to get t=5 as the final answer.

static int timeMax2(int[] arr) {
  int len = arr.length;
  int times[] = new int[len];
  for(int i=0; i<len; i++) {
    times[i] = 2*arr[i] + (i%2 == 0 ? 0 : 1);
  }

  Arrays.sort(times);

  int maxGuests = 0;
  int timeMax = 0;
  int guests = 0;
  for(int time : times) {
    if(time%2 == 0) {
      guests++;
      if(guests > maxGuests) {
        maxGuests = guests;
        timeMax = time;
      }
    } else {
      guests--;
    }
  }

  return timeMax/2;
}

Its Algorithmic crush , Hackerrank. Can be done in O(1) .. Crazy technique/

function getMaximumGuests(entryTimes) {
var hoursArray = new Array(25);
hoursArray.fill(0);
for (var i = 0; i < entryTimes.length; i++) {
var entryTime = entryTimes[i];
hoursArray[entryTime[0]]++;
hoursArray[entryTime[1] + 1]--;
}
var maxSum = 0;
var currentSum = 0;
for (var j = 1; j < hoursArray.length; j++) {
currentSum += hoursArray[j];
currentSum > maxSum ? maxSum = currentSum : "";
}
return maxSum;
}

var entryTimes = [[1, 4], [2, 5], [9, 12], [5, 9], [5, 12]];

console.log("Maximum entry time is ", getMaximumGuests(entryTimes));

function getMaximumGuests(entryTimes) {
  var hoursArray = new Array(25);
  hoursArray.fill(0);
  for (var i = 0; i < entryTimes.length; i++) {
    var entryTime = entryTimes[i];
    hoursArray[entryTime[0]]++;
    hoursArray[entryTime[1] + 1]--;
  }
  var maxSum = 0;
  var currentSum = 0;
  for (var j = 1; j < hoursArray.length; j++) {
    currentSum += hoursArray[j];
    currentSum > maxSum ? maxSum = currentSum : "";
  }
  return maxSum;
}

var entryTimes = [[1, 4], [2, 5], [9, 12], [5, 9], [5, 12]];

console.log("Maximum entry time is ", getMaximumGuests(entryTimes));

public static void register(int entry, int exit) {
    while (entry <= exit) {
      hourlyCount[entry]++;      
      if (hourlyCount[entry]>hourlyCount[maxGuestIndcator]){
        maxGuestIndcator=entry;
      }
      entry++;
    }   
  }
  private static int hourlyCount[] = new int[13];
  private static int maxGuestIndcator;