Kurapika and Friends

Moderate
0/80
profile
Contributed by
4 upvotes
Asked in companies
Google incAirtel

Problem statement

Kurapika is long lost from his friends. He wants to meet his friends. He has total ‘n’ friends, and everyone is not available on the same day. But he can meet his friends only once. Given two arrays, ‘s’ and ‘e’, where s[i] denotes the starting date when an ith friend is available, and e[i] denotes when the ith friend will not be available after this date. Help Kurapika to know what is the maximum number of friends he can meet on one single day.

For Example : 
s = {1, 4, 11} e = {9, 5, 13}

In the given example, the first friend is available between dates 1 to 9, the second is available on dates 4 and 5, and the third is available on dates 11 to 13. Hence he can meet a maximum of only two friends on dates 4 and 5.

Hence the answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’ denoting the total number of friends.

The second line of the test case denotes an array of ‘N’ integers ‘s’ denoting the starting date when the ith friend will be available.

The third line of the test case denotes an array of ‘N’ integers ‘e’ denoting the ending date when the ith friend will be available.
Output Format : 
For each test case, print a single integer “answer”, denoting the maximum number of friends he can meet.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 <= T <= 100    
1 <= N <= 5000
1 <= s[i], e[i] <= 10^9

Time limit: 1 sec
Sample Input 1 :
2
3
1 5 7
2 6 8
7
1 2 3 4 5 6 7
8 9 10 11 12 13 14
Sample Output 1 :
1
7
Explanation For Sample Input 1 :
In the first test case, there was no single day when more than 1 friend was available.

Hence the answer is 1.

In the second test case, all of the friends were available on day 7 and day 8. 

Hence the final answer is 7.
Sample Input 2 :
2
5
1 2 6 5 3
5 5 7 6 8
4
1 2 3 4
10 3 3 4
Sample Output 2 :
4
3
Hint

Take a map in which increment the index when his friends are available and decrement when his friends are not available

Approaches (1)
Hash Map

In this approach, we will take a map of integers in which we will increment the counter at index ‘i’ for every s[i] and decrement the counter of index ‘i’ for every index ‘i’ and return the day on which a maximum number of friends were present.

 

The steps are as follows: 

 

  • Take a map “available” in which we will store the count of the number of friends who are present.
  • Take an integer “answer” denoting the final answer and an integer “count” to store the current number of friends present.
  • Iterate through the loop from 0 to n-1(say iterator be i):
    • Increment the value of “available[s[i]]” and decrement the value of “available[e[i] + 1]”.
  • Iterate through the whole map “available”(say iterator be i):
    • Update the value of “counter” = i.second.
    • Update “answer” = max(“answer”, “counter”).
  • Return “answer”.
Time Complexity

O( N * log( N ) ), where N is the size of the array “loads”.

 

As we are Iterating through 0 to N and using a map to store and retrieve the values which takes log(N) time.

Hence the time complexity is O( N * log( N ) ).

Space Complexity

O( N )

 

Since we are using a map “available” which will store all the days.

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
Kurapika and Friends
Full screen
Console