Help needed in CHEFBDAY

Please explain the logic?

Given N friends with their arrival and departure time lets say ai and bi respectively.

Now you have Q queries asking the number of friends present at the party at time t.

Approach :

  1. if ith guest arrives at ai and leaves at bi, does it mean he is at his house at time b (ai and bi are inclusive duration for stay of a friend).

Explanation of sample case:


3 3

1 2

2 2

2 3





Friend       Arrival Time        Departure Time       Total Count
  1               1                   2                   1

  2               2                   2                  1st friend who arrived at t=1 
                                                         but departure time is t=2,
                                                         2nd and 3rd friend who arrived 
                                                         at t=2 and their departure time t=2 
                                                         and t=3 respectively. Since ai and bi 
                                                         are inclusive therefore total friends  
                                                         present are 1+1+1 = 3.

  3               2                   3                  1st friend who arrived at t=1 
                                                         has already left,
                                                         2nd friend who arrived 
                                                         at t=2 also left. Since departure 
                                                         time of 3rd is t=3, therefore total  
                                                         present is 1.

please explain the logic for its solution…since every solution i saw has nearly same logic u can explain this one-
I cant understand this in solution-count=count+start[i]-close[i-1]


All arrays when program runs succesfully on given sample case ( 1-based index )

// start and close arrays are formed using hashing i.e. counting how many arrived and departured at the same time.

// start    =    1 2 0
// close    =    0 2 1
// count    =    1 3 1
// time     =    1 3 1
remember start[0] = close[0] = 0 because nobody has arrived or departured at t=0.

Now he is starting from the first person and running till the last person(max)…

for ( i=1;i<=max;i++ )
         count += start[i] - close[i-1];                                      
         time[i] = count;                         

since he has the count of each friend’s arrival & departure stored in start and close array resp., therefore he is subtracting the count of (i-1)th person’s departure time from ith person’s arrival time and adding the result to the previous obtained result in order to get the count at time ti where i ∈ [1,max].

Now for every query ti, he simply outputs the value of time[ti] to get the final result.

Hope it is clear now.