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
Table of Contents
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.
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;
}
};
Code language: PHP (php)
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;
}
}
Code language: JavaScript (javascript)
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++
}
};
Code language: JavaScript (javascript)
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