An integer interval [a, b] (for integers a &lt; b) is a set of all consecutive integers from a to b, including a and b.

Find the minimum size of a set S such that for every integer interval A in intervals, the intersection of S with A has a size of at least two.

&nbsp;
Example 1:

Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3
Explanation: 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.


Example 2:

Input: intervals = [[1,2],[2,3],[2,4],[4,5]]
Output: 5
Explanation: An example of a minimum sized set is {1, 2, 3, 4, 5}.


&nbsp;
Constraints:


	1 &lt;= intervals.length &lt;= 3000
	intervals[i].length == 2
	0 &lt;= ai &lt;&nbsp;bi &lt;= 108


class Solution:
    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
        ans = []
        for x, y in sorted(intervals, key=lambda x: (x[1], -x[0])): 
            if not ans or ans[-2] < x: 
                if ans and x <= ans[-1]: ans.append(y)
                else: ans.extend([y-1, y])
        return len(ans)
//Time Complexity O(Nlog(N)) - N is the number of intervals
//Space Complexity O(N) - N is the number of intervals, can be reduced to O(1) if needed
class Solution {
    public int intersectionSizeTwo(int[][] intervals) {
        //corner case: can intervals be null or empty? No

        //First, sort the intervals by end, then by reverse order start
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                if (a[1] == b[1]) {
                    return b[0] - a[0];
                }
                return a[1] - b[1];
            }
        });

        //Second, for each two intervals, greedily find if the previous interval would satisfy next interval's request
        List<Integer> list = new ArrayList<>(); //basically the ending set S, btw, we actually do not need this but I use it here for better intuition

        //add last two nums within the range
        list.add(intervals[0][1] - 1);
        list.add(intervals[0][1]);

        for (int i = 1; i < intervals.length; i++) {
            int lastOne = list.get(list.size() - 1);
            int lastTwo = list.get(list.size() - 2);

            int[] interval = intervals[i];
            int start = interval[0];
            int end = interval[1];

            //if overlaps at least 2
            if (lastOne >= start && lastTwo >= start) {
                continue;
            } else if (lastOne >= start) { //if overlaps 1
                list.add(end);
            } else { //if not overlapping
                list.add(end - 1);
                list.add(end);
            }
        }

        return list.size();
    }
}
class Solution {
public:

    // sort wrt. end value

    static bool compare(vector<int>& a, vector<int>& b)
    {
        if(a[1] == b[1])
            return a[0] < b[0];
        else
            return a[1] < b[1];
    }

    int intersectionSizeTwo(vector<vector<int>>& intervals) {

        int n = intervals.size();

        // sort the array

        sort(intervals.begin(), intervals.end(), compare);

        vector<int> res;

        res.push_back(intervals[0][1] - 1);

        res.push_back(intervals[0][1]);

        for(int i = 1; i < n; i++)
        {
            int start = intervals[i][0];

            int end = intervals[i][1];

            if(start > res.back())
            {
                res.push_back(end - 1);

                res.push_back(end);
            }
            else if(start == res.back())
            {
                res.push_back(end);
            }
            else if(start > res[res.size() - 2])
            {
                res.push_back(end);
            }
        }

        return res.size();
    }
};
/**
 * @param {number[][]} intervals
 * @return {number}
 */
var intersectionSizeTwo = function(intervals) {
    const sortedIntervals = intervals.sort(sortEndsThenStarts)
    let currentTail = []
    let answer = 0
    sortedIntervals.forEach(interval => {
        const start = interval[0]
        const end = interval[1]
        const startPoint = currentTail[0]
        const lastPoint = currentTail[1]
        
        if (!currentTail.length || lastPoint < start){
            currentTail = [end -1, end]
            answer += 2
        } else if ( startPoint < start){
            currentTail = [currentTail[1], end]
            answer += 1
        }

    })
    return answer

};

function sortEndsThenStarts(intervalA, intervalB){
    return intervalA[1] < intervalB[1] ? -1 : 1
}
Set Intersection Size At Least Two