Help needed in CHEFBDAY

[akshayv3]

BIRTHDAY PARTY | CodeChef

Please explain the logic?

[rjohari23]

Given N friends with their arrival and departure time lets say a_i and b_i 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 a_i and leaves at b_i, does it mean he is at his house at time b (a_i and b_i are inclusive duration for stay of a friend).

Explanation of sample case:

1

3 3

1 2

2 2

2 3

1

2

3


Output:
1
3
1

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.

[rjohari23]

@akshayv3,

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 t_i where i ∈ [1,max].

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

Hope it is clear now.

[akshayv3]

please explain the logic for its solution…since every solution i saw has nearly same logic u can explain this one-http://www.codechef.com/viewsolution/6552547
I cant understand this in solution-count=count+start[i]-close[i-1]