Formatted question description: https://leetcode.ca/all/757.html

757. Set Intersection Size At Least Two (Hard)

An integer interval [a, b] (for integers a < b) is a set of all consecutive integers from a to b, including a and b.

Find the minimum size of a set S such that for every integer interval A in intervals, the intersection of S with A has a size of at least two.

Example 1:

Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3
Explanation: Consider the set S = {2, 3, 4}.  For each interval, there are at least 2 elements from S in the interval.
Also, there isn't a smaller size set that fulfills the above condition.
Thus, we output the size of this set, which is 3.


Example 2:

Input: intervals = [[1,2],[2,3],[2,4],[4,5]]
Output: 5
Explanation: An example of a minimum sized set is {1, 2, 3, 4, 5}.


Constraints:

• 1 <= intervals.length <= 3000
• intervals[i].length == 2
• 0 <= ai < bi <= 108

Related Topics:
Greedy

Solution 1. Greedy

Keep track of the two intersection points.

// OJ: https://leetcode.com/problems/set-intersection-size-at-least-two/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int intersectionSizeTwo(vector<vector<int>>& A) {
sort(begin(A), end(A), [](auto &a, auto &b) { return a[1] < b[1]; });
int ans = 0, a = INT_MIN, b = INT_MIN;
for (auto &v : A) {
if (v[0] > b) {
b = v[1];
a = v[1] - 1;
ans += 2;
} else if (v[0] > a) {
a = v[1];
if (a == b) --a;
else if (a > b) swap(a, b);
ans++;
}
}
return ans;
}
};

• class Solution {
public int intersectionSizeTwo(int[][] intervals) {
Arrays.sort(intervals, new Comparator<int[]>() {
public int compare(int[] interval1, int[] interval2) {
if (interval1[0] != interval2[0])
return interval1[0] - interval2[0];
else
return interval2[1] - interval1[1];
}
});
int length = intervals.length;
int[] remains = new int[length];
Arrays.fill(remains, 2);
int size = 0;
for (int i = length - 1; i >= 0; i--) {
int[] interval = intervals[i];
int start = interval[0], end = interval[1];
int remain = remains[i];
int intersectionStart = start, intersectionEnd = start + remain;
for (int j = intersectionStart; j < intersectionEnd; j++) {
for (int k = 0; k <= i; k++) {
if (remains[k] > 0 && j <= intervals[k][1])
remains[k]--;
}
size++;
}
}
return size;
}
}

############

class Solution {
public int intersectionSizeTwo(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]);
int ans = 0;
int s = -1, e = -1;
for (int[] v : intervals) {
int a = v[0], b = v[1];
if (a <= s) {
continue;
}
if (a > e) {
ans += 2;
s = b - 1;
e = b;
} else {
ans += 1;
s = e;
e = b;
}
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/set-intersection-size-at-least-two/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int intersectionSizeTwo(vector<vector<int>>& A) {
sort(begin(A), end(A), [](auto &a, auto &b) { return a[1] < b[1]; });
int ans = 0, a = INT_MIN, b = INT_MIN;
for (auto &v : A) {
if (v[0] > b) {
b = v[1];
a = v[1] - 1;
ans += 2;
} else if (v[0] > a) {
a = v[1];
if (a == b) --a;
else if (a > b) swap(a, b);
ans++;
}
}
return ans;
}
};

• class Solution:
def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
intervals.sort(key=lambda x: (x[1], -x[0]))
s = e = -1
ans = 0
for a, b in intervals:
if a <= s:
continue
if a > e:
ans += 2
s, e = b - 1, b
else:
ans += 1
s, e = e, b
return ans


• func intersectionSizeTwo(intervals [][]int) int {
sort.Slice(intervals, func(i, j int) bool {
a, b := intervals[i], intervals[j]
if a[1] == b[1] {
return a[0] > b[0]
}
return a[1] < b[1]
})
ans := 0
s, e := -1, -1
for _, v := range intervals {
a, b := v[0], v[1]
if a <= s {
continue
}
if a > e {
ans += 2
s, e = b-1, b
} else {
ans += 1
s, e = e, b
}
}
return ans
}