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.

A 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][0] < A[i][1] <= 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[1]>b[1])return false;
        if(a[1]==b[1])return a[0]>b[0];
        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[0][1]-1;
        int right=v[0][1];
        ans+=2;
        for(int i=1; i<v.size(); i++){
            vector<int>curr=v[i];
            if(left<curr[0] && curr[0]<=right){
                ans++;
                left=right;
                right=curr[1];
            }
            else if(curr[0]>right){
                ans+=2;
                left=curr[1]-1;
                right=curr[1];
            }
        }
        return ans;
    }
};