Welcome to Subscribe On Youtube
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 <= 3000intervals[i].length == 20 <= 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 }