Last Updated: 10 Sep, 2021

Kurapika and Friends

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 Approach

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”.

Solve now