757. Set Intersection Size At Least Two

757. Set Intersection Size At Least Two

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 size at least 2.

Example 1:

Input: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]Output: 3Explanation: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: 5Explanation:An example of a minimum sized set is {1, 2, 3, 4, 5}.

Note:

intervals will have length in range [1, 3000]. intervals[i] will have length 2, representing some integer interval. intervals[i][j] will be an integer in [0, 10^8].

class Solution { public int intersectionSizeTwo(int[][] intervals) { Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0]-b[0] : b[1]-a[1]); int[] todo = new int[intervals.length]; Arrays.fill(todo, 2); int ans = 0, t = intervals.length; while (--t >= 0) { int s = intervals[t][0]; int e = intervals[t][1]; int m = todo[t]; for (int p = s; p < s+m; ++p) { for (int i = 0; i <= t; ++i) if (todo[i] > 0 && p <= intervals[i][1]) todo[i]--; ans++; } } return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。