Justice league

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
0 upvote
Asked in companies
ShareChatCGIArgano

Problem statement

There are ‘N’ number of super heroes in DC and each superhero is building his/her team to have a last fight against Darkseid.

Each superhero has his/her criteria to take the candidate into their team in which each superhero has marked an interval (interval[i] = [lefti, righti], inclusive lefti and righti) of integers for which the candidate with a code name (code name is the integer value) will fit into their teams.

But superheroes give the candidates a chance to choose for which superhero team they are willing to work for.

All candidates decide to go into the team for which the size of the interval is minimum and their code name can reside inside the interval (The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1).

If the candidate has such a code name that no interval exists to reside him/her. Then he will not be eligible to take part in the Justice League.

You are Batman and you are managing the whole process, so your task is to make a list which contains the smallest size of interval in which each candidate resides for a team.

Note :

If the code name does not match any interval then print -1 for that code name.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer ‘T,’ denoting the number of test cases. The test cases follow:

The first line of each test case contains an integer ‘N’ denoting the number of super heroes.

The second line of each test case contains 2 * N space-separated integers of there presented in a 2 D array, say ‘intervals’ denoting the interval range for each superhero. 

The third line of each test case contains an integer ‘X’ denoting the number of candidates.

The fourth and the last line of each test case contains X single space separated integers represented in an array, say ‘codeNames’ denoting the code names for ‘X’ candidates.

Output Format:

Output contains ‘N’ single space separated integers denoting the smallest size of interval in which each candidate will reside.

Note:

You don’t need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 5 *10 ^ 2
1 <= X <= 5 * 10 ^ 2
Intervals[i].length = 2
1 <= lefti <= righti <= 5 * 10 ^ 2
1 <= codeNames[j] <= 5 * 10 ^ 2

Time Limit: 1 sec.
Sample Input 1:
2
4
1 4 2 4 3 6 4 4
4
2 3 4 5
4
2 3 2 5 1 8 20 25
4
2 19 5 22
Sample Output 1:
3 3 1 4  
2 -1 4 6
Explanation for Sample Input 1:
For test Case 1:
Code Name = 2: The interval [2, 4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
Code Name = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
Code Name = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
Code Name = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.
So the output will be 3 3 1 4.

For Test Case 2:
Code Name = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
Code Name = 19: None of the intervals contain 19. The answer is -1.
Code Name = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
Code Name = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.
So the output will be 2 -1 4 6.
Sample Input 2:
2
4
1 2 3 4 5 6 7 8
2
2 3
4
1 1 1 1 1 1 1 1
2
1 3
Sample Output 2:
2 2
1 -1
Hint

Can you think of a greedy approach considering the size of intervals in mind ?

Approaches (1)
Greedy

The idea is to sort the intervals according to the size of the intervals. Then iterate over the sorted intervals. For each interval, find the code name that lies within the interval.

 

The steps are as follows: 

  • Declare an unordered map, say ‘mp’ of type integer as key and array of integers as value as key value pair to store the indexes of ‘codeNames’.
  • Declare a set, say ‘s’ of integer type to store the values of ‘codeNames’.
  • Now sort the ‘intervals’ according to the increasing order of interval sizes.
  • Declare an array, say ‘ans’ of size equal to sizeof ‘codeName’ to store the final answer and initialize it with -1.
  • Iterate over the ‘codeNames’ and store the values in ‘mp’ and ‘s’.
  • Now make an iteration over the ‘intervals’ with the help of iterator ‘v’.
    • Store the lower bound of the ‘vth’ interval in a variable, say ‘l’ and upper bound in a variable, say ‘r’.
    • Now declare an array, say ‘rem’.
    • Now, for the interval, find the code names covered by that interval.
    • For that, find all the elements in the ‘s’ with lower bound as ‘l’ and store them in an iterator, say ‘it1’.
    • Similarly store for upper bound in iterator ‘it2’.
    • Now make an iteration from ‘it1’ to ‘it2’ with the help of the iterator ‘it’.
    • Store the value of ‘it’ in a variable, say ‘q’.
      • Now push this value ‘q’ in the declared array ‘rem’.
      • Now iterate for all the values in the ‘mp’ and store the r - l + 1 in ‘ans’.
    • Now remove the code names from the set ‘s’.
  • Return ‘ans’ to the given function.
Time Complexity

O(N * logN), where ‘N’ denotes the length of the ‘interval’ array.

 

As we are using a greedy method for this approach in which we have sorted ‘intervals’ in terms of size of the intervals. Therefore, overall time complexity will be O(N * logN).

Space Complexity

O(X), where ‘X’ denotes the size of the ‘codeName’ array.

 

As we are using auxiliary space for map and set to store the values in ‘codeName’. Therefore, overall space complexity will be O(X).

Code Solution
(100% EXP penalty)
Justice league
Full screen
Console