Last Updated: 11 Jul, 2021
Justice league
Moderate
Asked in companies
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.
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.
Approaches
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.