757. Set Intersection Size At Least Two

Description

You are given a 2D integer array intervals where intervals[i] = [start_i, end_i] represents all the integers from start_i to end_i 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 <= 3000
intervals[i].length == 2
0 <= start_i < end_i <= 10⁸

Solutions

Solution 1: Sorting + Greedy

We want to select as few integer points as possible on the number line such that each interval contains at least two points. A classic and effective strategy is to sort intervals by their right endpoints and try to place selected points towards the right side of intervals, so that these points can cover more subsequent intervals.

First, sort all intervals by the following rules:

Sort by right endpoint in ascending order;
If right endpoints are equal, sort by left endpoint in descending order.

The reason for this sorting is: intervals with smaller right endpoints have less "operational space" and should be satisfied first; when right endpoints are equal, intervals with larger left endpoints are narrower and should be prioritized.

Next, we use two variables \(s\) and \(e\) to record the second-to-last point and last point that are common to all currently processed intervals. Initially, \(s = e = -1\), indicating that no points have been placed yet.

Then we process the sorted intervals \([a, b]\) one by one, and discuss three cases based on their relationship with \(\{s, e\}\):

If \(a \leq s\): The current interval already contains both points \(s\) and \(e\), so no additional points are needed.
If \(s < a \leq e\): The current interval only contains one point (i.e., \(e\)), and needs one more point. To make the new point most helpful for subsequent intervals, we choose the rightmost point \(b\) in the interval. Update \(\textit{ans} = \textit{ans} + 1\), and set the new two points to \(\{e, b\}\).
If \(a > e\): The current interval does not contain either of the existing two points, so two points need to be added. The optimal choice is to place \(\{b - 1, b\}\) at the rightmost side of the interval. Update \(\textit{ans} = \textit{ans} + 2\), and set the new two points to \(\{b - 1, b\}\).

Finally, return the total number of points placed, \(\textit{ans}\).

The time complexity is \(O(n \times \log n)\) and the space complexity is \(O(\log n)\), where \(n\) is the number of intervals.

Python3JavaC++GoTypeScript

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

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

class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [&](vector<int>& a, vector<int>& b) {
            return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
        });
        int ans = 0;
        int s = -1, e = -1;
        for (auto& 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;
    }
};

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
}

function intersectionSizeTwo(intervals: number[][]): number {
    intervals.sort((a, b) => (a[1] !== b[1] ? a[1] - b[1] : b[0] - a[0]));
    let s = -1;
    let e = -1;
    let ans = 0;
    for (const [a, b] of intervals) {
        if (a <= s) {
            continue;
        }
        if (a > e) {
            ans += 2;
            s = b - 1;
            e = b;
        } else {
            ans += 1;
            s = e;
            e = b;
        }
    }
    return ans;
}

757. Set Intersection Size At Least Two

Description

Solutions

Solution 1: Sorting + Greedy

Comments