Last updated on January 29th, 2025 at 02:14 am
Here, we see a Set Intersection Size At Least Two LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Bit-Manipulation, Depth-First Search
Level of Question
Hard
Set Intersection Size At Least Two LeetCode Solution
Table of Contents
1. 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.
2. Coding Pattern Used in Solution
The provided code follows the Merge Intervals pattern. This pattern is commonly used when dealing with overlapping intervals, where the goal is to either merge, count, or manipulate intervals based on their overlaps.
3. Code Implementation in Different Languages
3.1 Set Intersection Size At Least Two 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;
}
};
3.2 Set Intersection Size At Least Two 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.3 Set Intersection Size At Least Two 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++
}
};
3.4 Set Intersection Size At Least Two 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
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n log n) | O(n) |
| Java | O(n log n) | O(n) |
| JavaScript | O(n log n) | O(n) |
| Python | O(n log n) | O(n) |