757. Set Intersection Size At Least Two LeetCode Solution

Last updated: February 20, 2025

In this guide, you will get 757. Set Intersection Size At Least Two LeetCode Solution with the best time and space complexity. The solution to Set Intersection Size At Least Two problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Set Intersection Size At Least Two solution in C++
Set Intersection Size At Least Two solution in Java
Set Intersection Size At Least Two solution in Python
Additional Resources

757. Set Intersection Size At Least Two LeetCode Solution image

Problem Statement of 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

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})

757. Set Intersection Size At Least Two LeetCode Solution in C++

class Solution {
 public:
  int intersectionSizeTwo(vector<vector<int>>& intervals) {
    int ans = 0;
    int mx = -1;
    int secondMax = -1;

    ranges::sort(intervals, [](const vector<int>& a, const vector<int>& b) {
      return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
    });

    for (const vector<int>& interval : intervals) {
      const int a = interval[0];
      const int b = interval[1];
      // The maximum and the second maximum still satisfy.
      if (mx >= a && secondMax >= a)
        continue;
      if (mx >= a) {  // The maximum still satisfy.
        secondMax = mx;
        mx = b;  // Add b to the set S.
        ans += 1;
      } else {              // The maximum and the second maximum can't satisfy.
        mx = b;             // Add b to the set S.
        secondMax = b - 1;  // Add b - 1 to the set S.
        ans += 2;
      }
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

757. Set Intersection Size At Least Two LeetCode Solution in Java

class Solution {
  public int intersectionSizeTwo(int[][] intervals) {
    int ans = 0;
    int mx = -1;
    int secondMax = -1;

    Arrays.sort(intervals,
                (a, b) -> a[1] == b[1] ? Integer.compare(b[0], a[0]) : Integer.compare(a[1], b[1]));

    for (int[] interval : intervals) {
      final int a = interval[0];
      final int b = interval[1];
      // The maximum and the second maximum still satisfy.
      if (mx >= a && secondMax >= a)
        continue;
      if (mx >= a) { // The maximum still satisfy.
        secondMax = mx;
        mx = b; // Add b to the set S.
        ans += 1;
      } else {             // The maximum and the second maximum can't satisfy.
        mx = b;            // Add b to the set S.
        secondMax = b - 1; // Add b - 1 to the set S.
        ans += 2;
      }
    }

    return ans;
  }
}
// code provided by PROGIEZ

757. Set Intersection Size At Least Two LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents