# Set Intersection InterviewBit | 757. Set Intersection Size At Least Two | Solution

## 757. Set Intersection Size At Least Two

You are given a 2D integer array `intervals` where `intervals[i] = [starti, endi]` represents all the integers from `starti` to `endi` inclusively.

containing set is an array `nums` where each interval from `intervals` has at least two integers in `nums`.

• For example, if `intervals = [[1,3], [3,7], [8,9]]`, then `[1,2,4,7,8,9]` and `[2,3,4,8,9]` are containing sets.

Return the minimum possible size of a containing set.

Example 1:

```Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5
Explanation: let nums = [2, 3, 4, 8, 9].
It can be shown that there cannot be any containing array of size 4.
```

Example 2:

```Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3
Explanation: let nums = [2, 3, 4].
It can be shown that there cannot be any containing array of size 2.
```

Example 3:

```Input: intervals = [[1,2],[2,3],[2,4],[4,5]]
Output: 5
Explanation: let nums = [1, 2, 3, 4, 5].
It can be shown that there cannot be any containing array of size 4.
```

Constraints:

• `1 <= intervals.length <= 3000`
• `intervals[i].length == 2`
• `0 <= starti < endi <= 108`

# Set Intersection

Problem Description

An integer interval [X, Y] (for integers X < Y) is a set of all consecutive integers from X to Y, including X and Y.
You are given a 2D array A with dimensions N x 2, where each row denotes an interval.
Find the minimum size of a set S such that for every integer interval Z in A, the intersection of S with Z has a size of at least two.

Problem Constraints
1 <= N <= 105
1 <= A[i] < A[i] <= 109

Input Format
The first argument is a 2D integer array A.

Output Format
Return a single integer denoting the minimum size of S.

Example Input
Input 1:

``````A = [[1, 3], [1, 4], [2, 5], [3, 5]]
``````

Input 2:

``````A = [[1, 2], [2, 3], [2, 4], [4, 5]]
``````

Example Output
Output 1:

``````3
``````

Output 2:

``````5
``````

Example Explanation
Explanation 1:

``````Consider the set S = {2, 3, 4}.  For each interval, there are at least 2 elements from S in the interval.
Also, there isn't a smaller size set that fulfills the above condition.
Thus, we output the size of this set, which is 3.``````

Explanation 2:

``An example of a minimum sized set is {1, 2, 3, 4, 5}.``

``class Solution {public:        static bool cmp(vector<int>&a, vector<int>&b){        if(a>b)return false;        if(a==b)return a>b;        return true;    }        int intersectionSizeTwo(vector<vector<int>>& v) {                int ans=0;        if(v.size()==0)return ans;        sort(v.begin(),v.end(),cmp);        int left=v-1;        int right=v;        ans+=2;        for(int i=1; i<v.size(); i++){            vector<int>curr=v[i];            if(left<curr && curr<=right){                ans++;                left=right;                right=curr;            }            else if(curr>right){                ans+=2;                left=curr-1;                right=curr;            }        }        return ans;    }};``