Minimum Sized Set

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

Problem statement

You are given 'N' sets. Each of the 'N' sets contains positive integers, and there are at least two elements in each set. The elements contained in each set can be determined from a 2D Matrix 'SETS' having 'N' rows and 2 columns. The 'i'th' set contains all the integers lying between 'SETS[i][0]' and 'SETS[i][1]' both inclusive.

Given the 2D Matrix 'SETS', your task is to find the minimum size of a set that contains at least two elements from each of the 'N' given sets.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T', denoting the number of test cases.

The first line of each test case contains an integer 'N', denoting the number of sets.

The second line of each test case contains 'N' space-separated integers denoting the first column of the matrix 'SETS'.

The third line of each test case contains 'N' space-separated integers denoting the second column of the matrix 'SETS'.
Output Format: 
For each test case, print the minimum size of a set that contains at least two elements from each of the 'N' given sets.

Print the output of each test case in a new line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N <= 10^5
1 <= SETS[i][j] < 10^9 

Where 'N' denotes the number of sets index, of the last checkpoint, and 'SETS[i][j]' denotes the element at the 'i'th' row and 'jth' column of the matrix 'SETS' respectively.

Time Limit: 1 sec
Sample Input 1:
2
3
1 2 4
4 4 5
2
1 3
3 5
Sample Output 1:
3
3
Explanation Of Sample Input 1:
For the first test case : 
The first set contains the integers {1, 2, 3, 4}. The second set contains the integers {2, 3, 4}. The third set contains the integers {4, 5}. 
The minimum sized set containing at least two elements from each set is {3, 4, 5} having 3 elements. Hence, the answer is 3 in this case.

For the second test case:
The minimum sized set containing at least two elements from each set is {2, 3, 4} having 3 elements. Hence, the answer is 3 in this case.
Sample Input 2:
2
3
1 2 5
3 4 6
3
1 2 3
6 3 4
Sample Output 2:
5
3
Explanation Of Sample Input 2:
For the first test case : 
The minimum sized set containing at least two elements from each set is {2, 3, 4, 5, 6} having 5 elements. Hence, the answer is 5 in this case.

For the second test case:
The minimum sized set containing at least two elements from each set is {2, 3, 4} having 3 elements. Hence, the answer is 3 in this case.
Hint

Try to think of an approach by sorting the sets on the basis of the maximum element in each set.

Approaches (1)
Sorting

The idea is to first sort the sets in increasing order based on the maximum element of each set. After sorting the sets, we will maintain two iterators pointing to the two greatest elements of our optimal set, i.e., the minimum sized set. We will initialize the pointers with the two greatest elements of the first set. Now we will iterate through all the other sets, and for each set, we will check whether the two stored greatest elements lie in the current set. If they both do not lie in the current set, then we will add two new elements to our optimal set. The two added elements will be the two greatest elements of the current set. Otherwise, if only the greatest element lies in the current set, then we will add only the greatest element of the current set to our optimal set. Otherwise, we do not need to add any new elements as at least two elements of the current set are already present in our optimal set. The final answer will be the size of our optimal set. In the cases when, when two sets have the same greatest element, we will iterate through the set having a greater minimum element first as it will be a subset of all the sets having a smaller minimum element and the same maximum element.

 

Steps: 

  1. Sort the array ‘SETS’ in ascending order based on the maximum element of each set, and in descending order based on the minimum element of each set when the maximum element of two sets are the same.
  2. Let ‘FIRSTGREATERELEMENT’ and ‘SECONDGREATERELEMENT’ be the two variables that store the maximum two values of our optimal set. Initialize ‘FIRSTGREATERELEMENT’ as ‘SETS[0][1]’ and ‘SECONDGREATERELEMENT’ as ‘SETS[0][1]’ - 1.
  3. Let 'MINSIZE' be the store the minimum size of the optimal set. Initialize it as 2, as we have added 2 values to the set.
  4. Iterate from ‘i’ = 1 to ‘N’ - 1.
    • If ‘FIRSTGREATERELEMENT’ is smaller than '
    • SETS[i][0], then
      • Set ‘FIRSTGREATERELEMENT’ as ‘SETS[i][1]’ and set ‘SECONDGREATERELEMENT’ as ‘SETS[i][1]’ - 1. Note that, we are adding the two greatest values in the i'th set as this will be the two elements having the greatest possibility to occur in the next iterations.
      • Increase 'MINSIZE' by 2 as we have added two new elements to our optimal set.
    • Otherwise, if ‘SECONDGREATERELEMENT’ is smaller than ‘SETS[i][0]’, then
      • Set ‘SECONDGREATERELEMENT’ as ‘FIRSTGREATERELEMENT’ and set ‘FIRSTGREATERELEMENT’ as ‘SETS[i][1]’. The ‘FIRSTGREATERELEMENT’ before this iteration now becomes the second greatest element of the optimal set.
      • Increase 'MINSIZE' by 1 as we have added an element to our optimal set.
  5. Return the variable 'MINSIZE'
Time Complexity

O(N*log(N)), where N is the number of sets.

 

Sorting the sets takes O(N*log(N)) time, and we are iterating through all the elements of the array SETS only once. Hence, the overall Time Complexity is O(N*log(N)).

Space Complexity

O(1)

 

We are using only constant extra space. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Minimum Sized Set
Full screen
Console