Last updated on October 9th, 2024 at 06:23 pm

Here, We see Set Intersection Size At Least Two LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Set Intersection Size At Least Two LeetCode Solution

Problem Statement

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.

1. Set Intersection Size At Least Two LeetCode Solution C++

class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) {
            return a[1] < b[1] || (a[1] == b[1] && a[0] > b[0]); 
        });
        int n = intervals.size(), ans = 0, p1 = -1, p2 = -1;
        for (int i = 0; i < n; i++) {
            if (intervals[i][0] <= p1) continue;
            if (intervals[i][0] > p2) {
                ans += 2;
                p2 = intervals[i][1];
                p1 = p2-1;
            }
            else {
                ans++;
                p1 = p2;
                p2 = intervals[i][1];
            }
        }
        return ans;
    }
};

2. Set Intersection Size At Least Two LeetCode Solution Java

import java.util.Arrays;

class Solution {
    public int intersectionSizeTwo(int[][] intervals) {
        int n = 0;
        long[] endStartPairs = new long[intervals.length];
        for (int[] interval : intervals) {
            endStartPairs[n] = -interval[0] & 0xFFFFFFFFL;
            endStartPairs[n++] |= (long) (interval[1]) << 32;
        }
        Arrays.sort(endStartPairs);
        int min = -2;
        int max = -1;
        int curStart;
        int curEnd;
        int res = 0;
        for (long endStartPair : endStartPairs) {
            curStart = -(int) endStartPair;
            curEnd = (int) (endStartPair >> 32);
            if (curStart <= min) {
                continue;
            }
            if (curStart <= max) {
                res += 1;
                min = max;
            } else {
                res += 2;
                min = curEnd - 1;
            }
            max = curEnd;
        }
        return res;
    }
}

3. Set Intersection Size At Least Two LeetCode Solution JavaScript

var intersectionSizeTwo = function (intervals) {
    intervals.sort((a, b) => a[0] - b[0])
    let setSize = 0, stack = [], i = 0
    while (true) {
        let l = i == intervals.length ? Number.MAX_SAFE_INTEGER : intervals[i][0]
        let r = i == intervals.length ? Number.MAX_SAFE_INTEGER : intervals[i][1]
        while (stack.length) {
            let min = stack.reduce((prev, item) => Math.min(prev, item[1] - item[2] + 1), Number.MAX_SAFE_INTEGER)
            if (min < l) {
                setSize++
                stack = stack.filter(item => {
                    if (item[2] == 1) return false
                    item[2]--
                    return true
                })
                continue
            }
            break
        }
        if (i == intervals.length) return setSize
        stack.push([l, r, 2])
        i++
    }
};

4. Set Intersection Size At Least Two LeetCode Solution Python

class Solution(object):
    def intersectionSizeTwo(self, intervals):
      intervals = sorted(intervals, key=lambda x:(x[1], -x[0]))
      e1, e2 = -1, -1
      ans = 0
      for s, e in intervals:
         if s > e2:
            e1, e2 = e-1, e
            ans += 2
         elif s > e1:
            e1, e2 = e2, e
            ans += 1
      return ans