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;
    }
};

Java

  • 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;
        }
    }
    
  • // 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;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions