Algorithm
Problem Name: 757. 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 <= 3000intervals[i].length == 20 <= starti < endi <= 108
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const intersectionSizeTwo = function(intervals) {
let highest = Number.NEGATIVE_INFINITY;
let secondHighest = Number.NEGATIVE_INFINITY;
return intervals
.sort((a, b) => a[1] - b[1])
.reduce((sum, interval) => {
if (interval[0] > secondHighest) {
secondHighest = interval[1];
highest = interval[1] - 1;
return sum + 2;
}
else if (interval[0] > highest) {
highest = secondHighest;
secondHighest = interval[1];
return sum + 1;
}
return sum;
}, 0);
};
Input
intervals = [[1,3],[3,7],[8,9]]
Output
5
#2 Code Example with Python Programming
Code -
Python Programming
class Solution(object):
def intersectionSizeTwo(self, intervals):
intervals.sort(key = lambda k: k[1])
solution = []
for start, end in intervals:
if not len(solution) or solution[-1] < start:
solution.append(end - 1)
solution.append(end)
elif solution[-2] < start:
solution.append(end)
return len(solution)
Input
intervals = [[1,3],[3,7],[8,9]]
Output
5